Search Results

Documents authored by Dumitrescu, Adrian

Document
DOI: 10.4230/LIPIcs.GD.2024.9
Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs

Authors: Adrian Dumitrescu and János Pach

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
A complete geometric graph consists of a set P of n points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant c < 1, such that every complete geometric graph on n points can be partitioned into at most cn plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set P is dense, which means that the ratio between the maximum and the minimum distances in P is of the order of Θ(√n).
Cite as

Adrian Dumitrescu and János Pach. Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 9:1-9:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.GD.2024.9,
  author =	{Dumitrescu, Adrian and Pach, J\'{a}nos},
  title =	{{Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{9:1--9:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.9},
  URN =		{urn:nbn:de:0030-drops-212939},
  doi =		{10.4230/LIPIcs.GD.2024.9},
  annote =	{Keywords: Convexity, complete geometric Graph, crossing Family, plane Subgraph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.42
Multiparty Selection

Authors: Ke Chen and Adrian Dumitrescu

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Given a sequence A of n numbers and an integer (target) parameter 1 ≤ i ≤ n, the (exact) selection problem is that of finding the i-th smallest element in A. An element is said to be (i,j)-mediocre if it is neither among the top i nor among the bottom j elements of S. The approximate selection problem is that of finding an (i,j)-mediocre element for some given i,j; as such, this variant allows the algorithm to return any element in a prescribed range. In the first part, we revisit the selection problem in the two-party model introduced by Andrew Yao (1979) and then extend our study of exact selection to the multiparty model. In the second part, we deduce some communication complexity benefits that arise in approximate selection. In particular, we present a deterministic protocol for finding an approximate median among k players.
Cite as

Ke Chen and Adrian Dumitrescu. Multiparty Selection. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2020.42,
  author =	{Chen, Ke and Dumitrescu, Adrian},
  title =	{{Multiparty Selection}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.42},
  URN =		{urn:nbn:de:0030-drops-133867},
  doi =		{10.4230/LIPIcs.ISAAC.2020.42},
  annote =	{Keywords: approximate selection, mediocre element, comparison algorithm, i-th order statistic, tournaments, quantiles, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.57
Sparse Hop Spanners for Unit Disk Graphs

Authors: Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
A unit disk graph G on a given set of points P in the plane is a geometric graph where an edge exists between two points p,q ∈ P if and only if |pq| ≤ 1. A subgraph G' of G is a k-hop spanner if and only if for every edge pq ∈ G, the topological shortest path between p,q in G' has at most k edges. We obtain the following results for unit disk graphs. 1) Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. 2) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. 3) Every n-vertex unit disk graph has a 2-hop spanner with O(nlog n) edges. This is the first nontrivial construction of 2-hop spanners. 4) For every sufficiently large n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. 5) For every point set on a circle, there exists a plane 4-hop spanner. As such, this provides a tight bound for points on a circle. 6) The maximum degree of k-hop spanners cannot be bounded from above by a function of k.
Cite as

Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth. Sparse Hop Spanners for Unit Disk Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.ISAAC.2020.57,
  author =	{Dumitrescu, Adrian and Ghosh, Anirban and T\'{o}th, Csaba D.},
  title =	{{Sparse Hop Spanners for Unit Disk Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.57},
  URN =		{urn:nbn:de:0030-drops-134018},
  doi =		{10.4230/LIPIcs.ISAAC.2020.57},
  annote =	{Keywords: graph approximation, \epsilon-net, hop-spanner, unit disk graph, lower bound}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.56
On the Stretch Factor of Polygonal Chains

Authors: Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P is the ratio between the total length of P and the distance of its endpoints, sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|. For a parameter c >= 1, we call P a c-chain if |p_ip_j|+|p_jp_k| <= c|p_ip_k|, for every triple (i,j,k), 1 <= i<j<k <= n. The stretch factor is a global property: it measures how close P is to a straight line, and it involves all the vertices of P; being a c-chain, on the other hand, is a fingerprint-property: it only depends on subsets of O(1) vertices of the chain. We investigate how the c-chain property influences the stretch factor in the plane: (i) we show that for every epsilon > 0, there is a noncrossing c-chain that has stretch factor Omega(n^{1/2-epsilon}), for sufficiently large constant c=c(epsilon); (ii) on the other hand, the stretch factor of a c-chain P is O(n^{1/2}), for every constant c >= 1, regardless of whether P is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain P in R^2 with n vertices, the minimum c >= 1 for which P is a c-chain in O(n^{2.5} polylog n) expected time and O(n log n) space.
Cite as

Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth. On the Stretch Factor of Polygonal Chains. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.MFCS.2019.56,
  author =	{Chen, Ke and Dumitrescu, Adrian and Mulzer, Wolfgang and T\'{o}th, Csaba D.},
  title =	{{On the Stretch Factor of Polygonal Chains}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.56},
  URN =		{urn:nbn:de:0030-drops-110005},
  doi =		{10.4230/LIPIcs.MFCS.2019.56},
  annote =	{Keywords: polygonal chain, vertex dilation, Koch curve, recursive construction}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.22
Convex Polygons in Cartesian Products

Authors: Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot

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

Abstract
We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
Cite as

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot. Convex Polygons in Cartesian Products. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{decarufel_et_al:LIPIcs.SoCG.2019.22,
  author =	{De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'{o}th, Csaba D. and Verdonschot, Sander},
  title =	{{Convex Polygons in Cartesian Products}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{22:1--22:17},
  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.22},
  URN =		{urn:nbn:de:0030-drops-104267},
  doi =		{10.4230/LIPIcs.SoCG.2019.22},
  annote =	{Keywords: Erd\H{o}s-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.30
A Product Inequality for Extreme Distances

Authors: Adrian Dumitrescu

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

Abstract
Let p_1,...,p_n be n distinct points in the plane, and assume that the minimum inter-point distance occurs s_{min} times, while the maximum inter-point distance occurs s_{max} times. It is shown that s_{min} s_{max} <= (9/8)n^2 + O(n); this settles a conjecture of Erdős and Pach (1990).
Cite as

Adrian Dumitrescu. A Product Inequality for Extreme Distances. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dumitrescu:LIPIcs.SoCG.2019.30,
  author =	{Dumitrescu, Adrian},
  title =	{{A Product Inequality for Extreme Distances}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{30:1--30:12},
  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.30},
  URN =		{urn:nbn:de:0030-drops-104343},
  doi =		{10.4230/LIPIcs.SoCG.2019.30},
  annote =	{Keywords: Extreme distances, repeated distances}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.13
Anchored Rectangle and Square Packings

Authors: Kevin Balas, Adrian Dumitrescu, and Csaba Tóth

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
For points p_1,...,p_n in the unit square [0,1]^2, an anchored rectangle packing consists of interior-disjoint axis-aligned empty rectangles r_1,...,r_n in [0,1]^2 such that point p_i is a corner of the rectangle r_i (that is, r_i is anchored at p_i) for i=1,...,n. We show that for every set of n points in [0,1]^2, there is an anchored rectangle packing of area at least 7/12-O(1/n), and for every n, there are point sets for which the area of every anchored rectangle packing is at most 2/3. The maximum area of an anchored square packing is always at least 5/32 and sometimes at most 7/27. The above constructive lower bounds immediately yield constant-factor approximations, of 7/12 -epsilon for rectangles and 5/32 for squares, for computing anchored packings of maximum area in O(n log n) time. We prove that a simple greedy strategy achieves a 9/47-approximation for anchored square packings, and 1/3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored rectangle and square packings in n^{O(1/epsilon)} and exp(poly(log (n/epsilon))) time, respectively.
Cite as

Kevin Balas, Adrian Dumitrescu, and Csaba Tóth. Anchored Rectangle and Square Packings. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{balas_et_al:LIPIcs.SoCG.2016.13,
  author =	{Balas, Kevin and Dumitrescu, Adrian and T\'{o}th, Csaba},
  title =	{{Anchored Rectangle and Square Packings}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.13},
  URN =		{urn:nbn:de:0030-drops-59054},
  doi =		{10.4230/LIPIcs.SoCG.2016.13},
  annote =	{Keywords: Rectangle packing, anchored rectangle, greedy algorithm, charging scheme, approximation algorithm.}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.36
On the Number of Maximum Empty Boxes Amidst n Points

Authors: Adrian Dumitrescu and Minghui Jiang

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We revisit the following problem (along with its higher dimensional variant): Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S. 1. We prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log n 2^alpha(n)), where alpha(n) is the extremely slowly growing inverse of Ackermann's function. The previous best bound, O(n^2), is due to Naamad, Lee, and Hsu (1984). 2. For any d at least 3, we prove that the number of maximum-volume empty boxes amidst n points in R^d is always O(n^d) and sometimes Omega(n^floor(d/2)). This is the first superlinear lower bound derived for this problem. 3. We discuss some algorithmic aspects regarding the search for a maximum empty box in R^3. In particular, we present an algorithm that finds a (1-epsilon)-approximation of the maximum empty box amidst n points in O(epsilon^{-2} n^{5/3} log^2{n}) time.
Cite as

Adrian Dumitrescu and Minghui Jiang. On the Number of Maximum Empty Boxes Amidst n Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.SoCG.2016.36,
  author =	{Dumitrescu, Adrian and Jiang, Minghui},
  title =	{{On the Number of Maximum Empty Boxes Amidst n Points}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.36},
  URN =		{urn:nbn:de:0030-drops-59281},
  doi =		{10.4230/LIPIcs.SoCG.2016.36},
  annote =	{Keywords: Maximum empty box, Davenport-Schinzel sequence, approximation algorithm, data mining.}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.128
Computing Opaque Interior Barriers à la Shermer

Authors: Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given polygon was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the polygon. In 1991 Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex n-gon. He conjectured that the barrier found by his algorithm is optimal, however this was refuted recently by Provan et al. Here we give a Shermer like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(n) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.
Cite as

Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth. Computing Opaque Interior Barriers à la Shermer. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 128-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.APPROX-RANDOM.2014.128,
  author =	{Dumitrescu, Adrian and Jiang, Minghui and T\'{o}th, Csaba D.},
  title =	{{Computing Opaque Interior Barriers \`{a} la Shermer}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{128--143},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.128},
  URN =		{urn:nbn:de:0030-drops-46938},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.128},
  annote =	{Keywords: Opaque barrier, approximation algorithm, isoperimetric inequality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.637
Bounds on the maximum multiplicity of some common geometric graphs

Authors: Adrian Dumitrescu, Andre Schulz, Adam Sheffer, and Csaba D. Toth

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We obtain new lower and upper bounds for the maximum multiplicity of some weighted, and respectively non-weighted, common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Omega (8.65^n) different triangulations. This improves the bound Omega (8.48^n) achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We present a new lower bound of Omega(11.97^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Omega(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.664^n) non-crossing spanning cycles. (iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(n log n) time algorithm for computing them.
Cite as

Adrian Dumitrescu, Andre Schulz, Adam Sheffer, and Csaba D. Toth. Bounds on the maximum multiplicity of some common geometric graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 637-648, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.STACS.2011.637,
  author =	{Dumitrescu, Adrian and Schulz, Andre and Sheffer, Adam and Toth, Csaba D.},
  title =	{{Bounds on the maximum multiplicity of some common geometric graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{637--648},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.637},
  URN =		{urn:nbn:de:0030-drops-30505},
  doi =		{10.4230/LIPIcs.STACS.2011.637},
  annote =	{Keywords: combinatorial geometry, matching, triangulation, spanning tree, spanning cycle, weighted structure, non-crossing condition}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2464
Dispersion in Unit Disks

Authors: Adrian Dumitrescu and Minghui Jiang

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We present two new approximation algorithms with (improved) constant ratios for selecting $n$ points in $n$ unit disks such that the minimum pairwise distance among the points is maximized. (I) A very simple $O(n \log{n})$-time algorithm with ratio $0.5110$ for disjoint unit disks. In combination with an algorithm of Cabello~\cite{Ca07}, it yields a $O(n^2)$-time algorithm with ratio of $0.4487$ for dispersion in $n$ not necessarily disjoint unit disks. (II) A more sophisticated LP-based algorithm with ratio $0.6495$ for disjoint unit disks that uses a linear number of variables and constraints, and runs in polynomial time. The algorithm introduces a novel technique which combines linear programming and projections for approximating distances. The previous best approximation ratio for disjoint unit disks was $\frac{1}{2}$. Our results give a partial answer to an open question raised by Cabello~\cite{Ca07}, who asked whether $\frac{1}{2}$ could be improved.
Cite as

Adrian Dumitrescu and Minghui Jiang. Dispersion in Unit Disks. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 299-310, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.STACS.2010.2464,
  author =	{Dumitrescu, Adrian and Jiang, Minghui},
  title =	{{Dispersion in Unit Disks}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{299--310},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2464},
  URN =		{urn:nbn:de:0030-drops-24646},
  doi =		{10.4230/LIPIcs.STACS.2010.2464},
  annote =	{Keywords: Dispersion problem, linear programming, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2465
Long Non-crossing Configurations in the Plane

Authors: Adrian Dumitrescu and Csaba D. Tóth

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We revisit several maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1993). Given a set of $n$ points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain new results for (b) and (c), as well as for the Hamiltonian cycle problem: (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio $\frac{2}{\pi+1} \approx 0.4829$. The previous best ratio, due to Alon et al., was $1/\pi \approx 0.3183$. Moreover, the ratio of our algorithm is close to $2/\pi$ on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio $0.502$ which runs in $O(n \log{n})$ time. The previous ratio, $1/2$, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster $O(n \log{n})$-time algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to $2/\pi$ on a relatively broad class of instances: for point sets with the product $\bf{\langle}$~diameter~$\times$ ~convex hull size $\bf{\rangle}$ much smaller than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. No previous approximation results were known for this problem.
Cite as

Adrian Dumitrescu and Csaba D. Tóth. Long Non-crossing Configurations in the Plane. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 311-322, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:LIPIcs.STACS.2010.2465,
  author =	{Dumitrescu, Adrian and T\'{o}th, Csaba D.},
  title =	{{Long Non-crossing Configurations in the Plane}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{311--322},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2465},
  URN =		{urn:nbn:de:0030-drops-24655},
  doi =		{10.4230/LIPIcs.STACS.2010.2465},
  annote =	{Keywords: Longest non-crossing Hamiltonian path, longest non-crossing Hamiltonian cycle, longest non-crossing spanning tree, approximation algorithm.}
}
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 About DROPS Imprint Privacy Contact