DROPS

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-dev.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-dev.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.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-dev.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}
}

3 Search Results for "Jiang, Minghui"

On the Number of Maximum Empty Boxes Amidst n Points

Abstract

Cite as

Computing Opaque Interior Barriers à la Shermer

Abstract

Cite as

Dispersion in Unit Disks

Abstract

Cite as

Thanks for your feedback!

Could not send message