10 Search Results for "Halperin, Dan"

Document
DOI: 10.4230/LIPIcs.ESA.2024.64
A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs

Authors: Kou Hamada, Sankardeep Chakraborty, Seungbum Jo, Takuto Koriyama, Kunihiko Sadakane, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Tree covering is a technique for decomposing a tree into smaller sized trees with desirable properties, and has been employed in various succinct data structures. However, significant hurdles stand in the way of a practical implementation of tree covering: a lot of pointers are used to maintain the tree-covering hierarchy and many indices for tree navigational queries consume theoretically negligible yet practically vast space. To tackle these problems, we propose a simple representation of tree covering using a balanced-parenthesis representation. The key to the proposal is the observation that every micro tree splits into at most two intervals on the BP representation. Utilizing the representation, we propose several data structures that represent a tree and its tree cover, which consequently allow micro tree compression with arbitrary coding and efficient tree navigational queries. We also applied our data structure to average-case optimal RMQ by Munro et al. [ESA 2021] and implemented the RMQ data structure. Our RMQ data structures spend less than 2n bits and process queries in a practical time on several settings of the performance evaluation, reducing the gap between theoretical space complexity and actual space consumption. For example, our implementation consumes 1.822n bits and processes queries in 5µs on average for random queries and in 13µs on average for the worst query widths. We also implement tree navigational operations while using the same amount of space as the RMQ data structures. We believe the representation can be widely utilized for designing practically memory-efficient data structures based on tree covering.
Cite as

Kou Hamada, Sankardeep Chakraborty, Seungbum Jo, Takuto Koriyama, Kunihiko Sadakane, and Srinivasa Rao Satti. A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hamada_et_al:LIPIcs.ESA.2024.64,
  author =	{Hamada, Kou and Chakraborty, Sankardeep and Jo, Seungbum and Koriyama, Takuto and Sadakane, Kunihiko and Satti, Srinivasa Rao},
  title =	{{A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{64:1--64:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.64},
  URN =		{urn:nbn:de:0030-drops-211359},
  doi =		{10.4230/LIPIcs.ESA.2024.64},
  annote =	{Keywords: Hypersuccinct trees, Succinct data structures, Range minimum queries, Binary trees}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2024.8
Scalable Harmonious Simplification of Isolines

Authors: Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
Isolines visually characterize scalar fields by connecting all points of the same value by a closed curve at repeated intervals. They work only as a set which gives the viewer an indication of the shape of the underlying field. Hence, when simplifying isolines it is important that the correspondence - the harmony - between adjacent isolines is preserved whenever it is present. The majority of state-of-the-art simplification methods treat isolines independently; at best they avoid collisions between adjacent simplified isolines. A notable exception is the work by Van Goethem et al. (2021) who were the first to introduce the concept of harmony between adjacent isolines explicitly as an algorithmic design principle. They presented a proof-of-concept algorithm that harmoniously simplifies a sequence of polylines. However, the sets of isolines of scalar fields, most notably terrain, consist of closed curves which are nested in arbitrarily complex ways and not of an ordered sequence of polylines. In this paper we significantly extend the work by Van Goethem et al. (2021) to capture harmony in general sets of isolines. Our new simplification algorithm can handle sets of isolines describing arbitrary scalar fields and is more efficient, allowing us to harmoniously simplify terrain with hundreds of thousands of vertices. We experimentally compare our method to the results of Van Goethem et al. (2021) on bundles of isolines and to general simplification methods on isolines extracted from DEMs of Antartica. Our results indicate that our method efficiently preserves the harmony in the simplified maps, which are thereby less noisy, cartographically more meaningful, and easier to read.
Cite as

Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann. Scalable Harmonious Simplification of Isolines. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vandenbroek_et_al:LIPIcs.COSIT.2024.8,
  author =	{van den Broek, Steven and Meulemans, Wouter and Reimer, Andreas and Speckmann, Bettina},
  title =	{{Scalable Harmonious Simplification of Isolines}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.8},
  URN =		{urn:nbn:de:0030-drops-208230},
  doi =		{10.4230/LIPIcs.COSIT.2024.8},
  annote =	{Keywords: Simplification, isolines, harmony}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.53
Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy

Authors: Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle; and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth - a class including, among others, all graphs of bounded genus.
Cite as

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.ICALP.2024.53,
  author =	{Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ramanujan, M. S.},
  title =	{{Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{53:1--53:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.53},
  URN =		{urn:nbn:de:0030-drops-201968},
  doi =		{10.4230/LIPIcs.ICALP.2024.53},
  annote =	{Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.99
Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number

Authors: Boris Klemz and Marie Diana Sieper

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Level Planarity, each level y is equipped with a partial order ≺_y on its vertices and in the desired drawing the left-to-right order of vertices on level y has to be a linear extension of ≺_y. Constrained Level Planarity is known to be a remarkably difficult problem: previous results by Klemz and Rote [ACM Trans. Alg.'19] and by Brückner and Rutter [SODA'17] imply that it remains NP-hard even when restricted to graphs whose tree-depth and feedback vertex set number are bounded by a constant and even when the instances are additionally required to be either proper, meaning that each edge spans two consecutive levels, or ordered, meaning that all given partial orders are total orders. In particular, these results rule out the existence of FPT-time (even XP-time) algorithms with respect to these and related graph parameters (unless P=NP). However, the parameterized complexity of Constrained Level Planarity with respect to the vertex cover number of the input graph remained open. In this paper, we show that Constrained Level Planarity can be solved in FPT-time when parameterized by the vertex cover number. In view of the previous intractability statements, our result is best-possible in several regards: a speed-up to polynomial time or a generalization to the aforementioned smaller graph parameters is not possible, even if restricting to proper or ordered instances.
Cite as

Boris Klemz and Marie Diana Sieper. Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 99:1-99:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{klemz_et_al:LIPIcs.ICALP.2024.99,
  author =	{Klemz, Boris and Sieper, Marie Diana},
  title =	{{Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{99:1--99:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.99},
  URN =		{urn:nbn:de:0030-drops-202428},
  doi =		{10.4230/LIPIcs.ICALP.2024.99},
  annote =	{Keywords: Parameterized Complexity, Graph Drawing, Planar Poset Diagram, Level Planarity, Constrained Level Planarity, Vertex Cover, FPT, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.35
Multi-Robot Motion Planning for Unit Discs with Revolving Areas

Authors: Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, and Erin Taylor

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study the problem of motion planning for a collection of n labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radius 2 disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a weakly-monotone motion plan, in which robots move according to an ordering as follows: during the turn of a robot R in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As R passes through a revolving area, a robot R' that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time (1+ε)-approximation algorithm. On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an O(1) factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time O(log n log log n)-approximation algorithm for this problem.
Cite as

Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, and Erin Taylor. Multi-Robot Motion Planning for Unit Discs with Revolving Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.35,
  author =	{Agarwal, Pankaj K. and Geft, Tzvika and Halperin, Dan and Taylor, Erin},
  title =	{{Multi-Robot Motion Planning for Unit Discs with Revolving Areas}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.35},
  URN =		{urn:nbn:de:0030-drops-173204},
  doi =		{10.4230/LIPIcs.ISAAC.2022.35},
  annote =	{Keywords: motion planning, optimal motion planning, approximation, complexity, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.12
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

Authors: Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We consider the unlabeled motion-planning problem of m unit-disc robots moving in a simple polygonal workspace of n edges. The goal is to find a motion plan that moves the robots to a given set of m target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time O(n log n + mn + m²) if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance 4 apart, any two target positions are at least distance 4 apart, and any pair of a start and a target positions is at least distance 3 apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.
Cite as

Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot. Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{banyassady_et_al:LIPIcs.SoCG.2022.12,
  author =	{Banyassady, Bahareh and de Berg, Mark and Bringmann, Karl and Buchin, Kevin and Fernau, Henning and Halperin, Dan and Kostitsyna, Irina and Okamoto, Yoshio and Slot, Stijn},
  title =	{{Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.12},
  URN =		{urn:nbn:de:0030-drops-160203},
  doi =		{10.4230/LIPIcs.SoCG.2022.12},
  annote =	{Keywords: motion planning, computational geometry, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.41
Throwing a Sofa Through the Window

Authors: Dan Halperin, Micha Sharir, and Itay Yehuda

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study several variants of the problem of moving a convex polytope K, with n edges, in three dimensions through a flat rectangular (and sometimes more general) window. Specifically: ii) We study variants where the motion is restricted to translations only, discuss situations where such a motion can be reduced to sliding (translation in a fixed direction), and present efficient algorithms for those variants, which run in time close to O(n^{8/3}). iii) We consider the case of a gate (an unbounded window with two parallel infinite edges), and show that K can pass through such a window, by any collision-free rigid motion, iff it can slide through it, an observation that leads to an efficient algorithm for this variant too. iv) We consider arbitrary compact convex windows, and show that if K can pass through such a window W (by any motion) then K can slide through a slab of width equal to the diameter of W. v) We show that if a purely translational motion for K through a rectangular window W exists, then K can also slide through W keeping the same orientation as in the translational motion. For a given fixed orientation of K we can determine in linear time whether K can translate (and hence slide) through W keeping the given orientation, and if so plan the motion, also in linear time. vi) We give an example of a polytope that cannot pass through a certain window by translations only, but can do so when rotations are allowed. vii) We study the case of a circular window W, and show that, for the regular tetrahedron K of edge length 1, there are two thresholds 1 > δ₁≈ 0.901388 > δ₂≈ 0.895611, such that (a) K can slide through W if the diameter d of W is ≥ 1, (b) K cannot slide through W but can pass through it by a purely translational motion when δ₁ ≤ d < 1, (c) K cannot pass through W by a purely translational motion but can do it when rotations are allowed when δ₂ ≤ d < δ₁, and (d) K cannot pass through W at all when d < δ₂. viii) Finally, we explore the general setup, where we want to plan a general motion (with all six degrees of freedom) for K through a rectangular window W, and present an efficient algorithm for this problem, with running time close to O(n⁴).
Cite as

Dan Halperin, Micha Sharir, and Itay Yehuda. Throwing a Sofa Through the Window. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{halperin_et_al:LIPIcs.SoCG.2021.41,
  author =	{Halperin, Dan and Sharir, Micha and Yehuda, Itay},
  title =	{{Throwing a Sofa Through the Window}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.41},
  URN =		{urn:nbn:de:0030-drops-138409},
  doi =		{10.4230/LIPIcs.SoCG.2021.41},
  annote =	{Keywords: Motion planning, Convex polytopes in 3D}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.26
Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead

Authors: Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of n unit discs under insertions in O(k log^2 n) update time and O(n) space, where k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has O(log^2 n) update time and O(log n) vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in O(log n) time, using tentative binary search; the lower envelopes are special in that at x=-infty any pseudo-line contributing to the first envelope lies below every pseudo-line contributing to the second envelope. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with O(n log n) preprocessing time, O(n^{1/2+epsilon} + l) query time and O(log^2 n) amortized update time, where l is the size of the output and for any epsilon>0. The structure requires O(n) storage space.
Cite as

Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer. Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.26,
  author =	{Agarwal, Pankaj K. and Cohen, Ravid and Halperin, Dan and Mulzer, Wolfgang},
  title =	{{Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.26},
  URN =		{urn:nbn:de:0030-drops-104307},
  doi =		{10.4230/LIPIcs.SoCG.2019.26},
  annote =	{Keywords: lower envelopes, pseudo-lines, unit discs, range search, dynamic algorithms, tentative binary search}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.76
Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching

Authors: Kiril Solovey and Dan Halperin

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We describe a general probabilistic framework to address a variety of Fréchet-distance optimization problems. Specifically, we are interested in finding minimal bottleneck-paths in d-dimensional Euclidean space between given start and goal points, namely paths that minimize the maximal value over a continuous cost map. We present an efficient and simple sampling-based framework for this problem, which is inspired by, and draws ideas from, techniques for robot motion planning. We extend the framework to handle not only standard bottleneck pathfinding, but also the more demanding case, where the path needs to be monotone in all dimensions. Finally, we provide experimental results of the framework on several types of problems.
Cite as

Kiril Solovey and Dan Halperin. Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{solovey_et_al:LIPIcs.ESA.2016.76,
  author =	{Solovey, Kiril and Halperin, Dan},
  title =	{{Sampling-Based Bottleneck Pathfinding with Applications to Fr\'{e}chet Matching}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{76:1--76:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.76},
  URN =		{urn:nbn:de:0030-drops-64179},
  doi =		{10.4230/LIPIcs.ESA.2016.76},
  annote =	{Keywords: Computational geometry, Fr\'{e}chet distances, sampling-based algorithms, random geometric graphs, bottleneck pathfinding}
}
Document
DOI: 10.4230/DagSemRep.372
Computational Geometry (Dagstuhl Seminar 03121)

Authors: Dan Halperin and Günter Rote

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Dan Halperin and Günter Rote. Computational Geometry (Dagstuhl Seminar 03121). Dagstuhl Seminar Report 372, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{halperin_et_al:DagSemRep.372,
  author =	{Halperin, Dan and Rote, G\"{u}nter},
  title =	{{Computational Geometry (Dagstuhl Seminar 03121)}},
  pages =	{1--6},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{372},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.372},
  URN =		{urn:nbn:de:0030-drops-152529},
  doi =		{10.4230/DagSemRep.372},
}
  • Refine by Author
  • 6 Halperin, Dan
  • 2 Agarwal, Pankaj K.
  • 1 Banyassady, Bahareh
  • 1 Bringmann, Karl
  • 1 Buchin, Kevin
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Computational geometry
  • 1 Human-centered computing → Graph drawings
  • 1 Information systems → Geographic information systems
  • 1 Mathematics of computing → Graphs and surfaces
  • 1 Mathematics of computing → Paths and connectivity problems
  • Show More...

  • Refine by Keyword
  • 2 motion planning
  • 1 Binary trees
  • 1 Computational Geometry
  • 1 Computational geometry
  • 1 Constrained Level Planarity
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 4 2024
  • 2 2022
  • 1 2003
  • 1 2016
  • 1 2019
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact