Space-Efficient Plane-Sweep Algorithms

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 $\mathrm{\Theta }(s)$ bits, where $\lg n \leq s \leq n \cdot \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\mathrm{/}s+n\cdot \lg s)$ time. We also give a simple algorithm to enumerate the intersections of $n$ line segments that runs in $O((n^2\mathrm{/}{s}^{2\mathrm{/}3})\cdot \lg s+k)$ time, where $k$ is the number of intersections. The counting version can be solved in $O((n^2\mathrm{/}{s}^{2\mathrm{/}3})\cdot \lg s)$~time. When the segments are axis-parallel, we give an $O((n^2\mathrm{/}s)\cdot {\lg }^{4\mathrm{/}3}s+n^{4\mathrm{/}3}\cdot {\lg }^{1\mathrm{/}3}n)$-time algorithm for counting the intersections, and an algorithm for enumerating the intersections that runs in $O((n^2/s) \cdot \lg s \cdot \lg \lg s + n \cdot \lg s + k)$time,where$k$ is the number of intersections. We finally present an algorithm that runs in $O((n^2/s + n \cdot \lg s) \cdot \sqrt{(n/s) \cdot \lg n})$ time to calculate Klee’s measure of axis-parallel rectangles.