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.ISAAC.2016.30
URN: urn:nbn:de:0030-drops-68009
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6800/
Go to the corresponding LIPIcs Volume Portal

Elmasry, Amr ; Kammer, Frank

Space-Efficient Plane-Sweep Algorithms

pdf-format:
LIPIcs-ISAAC-2016-30.pdf (0.4 MB)

Abstract

We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It is assumed that the input is in a read-only array of n items and that the available workspace is Theta(s) bits, where lg n <= s <= n * lg n. Three techniques that can be used as general tools in different space-efficient algorithms are introduced and employed within our algorithms. In particular, we give an almost-optimal algorithm for finding the closest pair among a set of n points that runs in O(n^2 /s + n * lg s) time. We also give a simple algorithm to enumerate the intersections of n line segments that runs in O((n^2 /s^{2/3}) * lg s + k) time, where k is the number of intersections. The counting version can be solved in O((n^2/s^{2/3}) * lg s) time. When the segments are axis-parallel, we give an O((n^2/s) * lg^{4/3} s + n^{4/3} * lg^{1/3} n)-time algorithm that counts the intersections and an O((n^2/s) * lg s * lg lg s + n * lg s + k)-time algorithm that enumerates the intersections, where k is the number of intersections. We finally present an algorithm that runs in O((n^2 /s + n * lg s) * sqrt{(n/s) * lg n}) time to calculate Klee's measure of axis-parallel rectangles.

BibTeX - Entry

@InProceedings{elmasry_et_al:LIPIcs:2016:6800,
  author =	{Amr Elmasry and Frank Kammer},
  title =	{{Space-Efficient Plane-Sweep Algorithms}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6800},
  URN =		{urn:nbn:de:0030-drops-68009},
  doi =		{10.4230/LIPIcs.ISAAC.2016.30},
  annote =	{Keywords: closest pair, line-segments intersection, Klee's measure}
}

Keywords: closest pair, line-segments intersection, Klee's measure
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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