Space-efficient plane-sweep algorithms

DOI10.4230/LIPICS.ISAAC.2016.30MaRDI QIDQ4636513zbMATH OpenOpenAlexFDO

Authors Amr Elmasry, Frank Kammer

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1507.01767

zbMATH Keywords

closest pairKlee's measureline-segments intersection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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 $lgnleqsleqncdotlgn$. 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+ncdotlgs)$ time. We also give a simple algorithm to enumerate the intersections of $n$ line segments that runs in $O((n^2/s^{2/3})cdotlgs+k)$ time, where $k$ is the number of intersections. The counting version can be solved in $O((n^2/s^{2/3})cdotlgs)$~time. When the segments are axis-parallel, we give an $O((n^2/s)cdotl{g}^{4/3}s+n^{4/3}cdotl{g}^{1/3}n)$-time algorithm for counting the intersections, and an algorithm for enumerating the intersections that runs in $O((n^2/s)cdotlgscdotlglgs+ncdotlgs+k)$ time, where $k$ is the number of intersections. We finally present an algorithm that runs in $O((n^2/s+ncdotlgs)cdotsqrt(n/s)cdotlgn)$ time to calculate Klee's measure of axis-parallel rectangles.

Recommendations

• Topologically sweeping an arrangement
• An in-place algorithm for Klee's measure problem in two dimensions
• Space-efficient geometric divide-and-conquer algorithms
• Space searching for intersecting objects
• Line-segment intersection made in-place

Cited in

(9)

• Succinct planar encoding with minor operations
• Simple 2^f-Color Choice Dictionaries
• Extra space during initialization of succinct data structures and dynamical initializable arrays
• Topologically sweeping an arrangement
• Line-segment intersection made in-place
• A plane-sweep algorithm for finding a closest pair among convex planar objects
• Space efficient linear time algorithms for BFS, DFS and applications
• Space-efficient geometric divide-and-conquer algorithms
• Space-efficient biconnected components and recognition of outerplanar graphs

This page was built for publication: Space-efficient plane-sweep algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636513)