License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.719
URN: urn:nbn:de:0030-drops-51353
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5135/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M. ; Tsakalidis, Konstantinos

Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings

pdf-format:
52.pdf (0.5 MB)

Abstract

We present optimal deterministic algorithms for constructing shallow cuttings in an arrangement of lines in two dimensions or planes in three dimensions. Our results improve the deterministic polynomial-time algorithm of Matousek (1992) and the optimal but randomized algorithm of Ramos (1999). This leads to efficient derandomization of previous algorithms for numerous well-studied problems in computational geometry, including halfspace range reporting in 2-d and 3-d, k nearest neighbors search in 2-d, (<= k)-levels in 3-d, order-k Voronoi diagrams in 2-d, linear programming with k violations in 2-d, dynamic convex hulls in 3-d, dynamic nearest neighbor search in 2-d, convex layers (onion peeling) in 3-d, epsilon-nets for halfspace ranges in 3-d, and more. As a side product we also describe an optimal deterministic algorithm for constructing standard (non-shallow) cuttings in two dimensions, which is arguably simpler than the known optimal algorithms by Matousek (1991) and Chazelle (1993).

BibTeX - Entry

@InProceedings{chan_et_al:LIPIcs:2015:5135,
  author =	{Timothy M. Chan and Konstantinos Tsakalidis},
  title =	{{Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{719--732},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5135},
  URN =		{urn:nbn:de:0030-drops-51353},
  doi =		{10.4230/LIPIcs.SOCG.2015.719},
  annote =	{Keywords: shallow cuttings, derandomization, halfspace range reporting, geometric data structures}
}

Keywords: shallow cuttings, derandomization, halfspace range reporting, geometric data structures
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI