Elmasry, Amr ;
Kammer, Frank
SpaceEfficient PlaneSweep Algorithms
Abstract
We introduce spaceefficient planesweep algorithms for basic planar geometric problems. It is assumed that the input is in a readonly 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 spaceefficient algorithms are introduced and employed within our algorithms. In particular, we give an almostoptimal 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 axisparallel, 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 axisparallel rectangles.
BibTeX  Entry
@InProceedings{elmasry_et_al:LIPIcs:2016:6800,
author = {Amr Elmasry and Frank Kammer},
title = {{SpaceEfficient PlaneSweep Algorithms}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {30:130:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6800},
URN = {urn:nbn:de:0030drops68009},
doi = {10.4230/LIPIcs.ISAAC.2016.30},
annote = {Keywords: closest pair, linesegments intersection, Klee's measure}
}
07.12.2016
Keywords: 

closest pair, linesegments intersection, Klee's measure 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

07.12.2016 