DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2017.2

Permuting and Batched Geometric Lower Bounds in the I/O Model

Authors: Peyman Afshani and Ingo van Duijn

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We study permuting and batched orthogonal geometric reporting problems in the External Memory Model (EM), assuming indivisibility of the input records. Our main results are twofold. First, we prove a general simulation result that essentially shows that any permutation algorithm (resp. duplicate removal algorithm) that does alpha*N/B I/Os (resp. to remove a fraction of the existing duplicates) can be simulated with an algorithm that does alpha phases where each phase reads and writes each element once, but using a factor alpha smaller block size. Second, we prove two lower bounds for batched rectangle stabbing and batched orthogonal range reporting queries. Assuming a short cache, we prove very high lower bounds that currently are not possible with the existing techniques under the tall cache assumption.

Cite as

Peyman Afshani and Ingo van Duijn. Permuting and Batched Geometric Lower Bounds in the I/O Model. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ESA.2017.2,
  author =	{Afshani, Peyman and van Duijn, Ingo},
  title =	{{Permuting and Batched Geometric Lower Bounds in the I/O Model}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.2},
  URN =		{urn:nbn:de:0030-drops-78695},
  doi =		{10.4230/LIPIcs.ESA.2017.2},
  annote =	{Keywords: I/O Model, Batched Geometric Queries, Lower Bounds, Permuting}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2016.60

Applications of Incidence Bounds in Point Covering Problems

Authors: Peyman Afshani, Edvin Berglin, Ingo van Duijn, and Jesper Sindahl Nielsen

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

Abstract

In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalization of Line Cover, the task is to cover the points using curves with d degrees of freedom. Another generalization is the Hyperplane Cover problem where points in d-dimensional space are to be covered by hyperplanes. All these problems have kernels of polynomial size, where the parameter is the minimum number of lines, curves, or hyperplanes needed. First we give a non-parameterized algorithm for both problems in O*(2^n) (where the O*(.) notation hides polynomial factors of n) time and polynomial space, beating a previous exponential-space result. Combining this with incidence bounds similar to the famous Szemeredi-Trotter bound, we present a Curve Cover algorithm with running time O*((Ck/log k)^((d-1)k)), where C is some constant. Our result improves the previous best times O*((k/1.35)^k) for Line Cover (where d=2), O*(k^(dk)) for general Curve Cover, as well as a few other bounds for covering points by parabolas or conics. We also present an algorithm for Hyperplane Cover in R^3 with running time O*((Ck^2/log^(1/5) k)^k), improving on the previous time of O*((k^2/1.3)^k).

Cite as

Peyman Afshani, Edvin Berglin, Ingo van Duijn, and Jesper Sindahl Nielsen. Applications of Incidence Bounds in Point Covering Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2016.60,
  author =	{Afshani, Peyman and Berglin, Edvin and van Duijn, Ingo and Sindahl Nielsen, Jesper},
  title =	{{Applications of Incidence Bounds in Point Covering Problems}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{60:1--60:15},
  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.60},
  URN =		{urn:nbn:de:0030-drops-59527},
  doi =		{10.4230/LIPIcs.SoCG.2016.60},
  annote =	{Keywords: Point Cover, Incidence Bounds, Inclusion Exclusion, Exponential Algorithm}
}

Search Results

Documents authored by van Duijn, Ingo

Permuting and Batched Geometric Lower Bounds in the I/O Model

Abstract

Cite as

Applications of Incidence Bounds in Point Covering Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message