Document

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

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.

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

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

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.

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

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

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.

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

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail