Space-Efficient Plane-Sweep Algorithms

2015/07/07 by Amr Elmasry, Elmasry, Amr, Frank Kammer +1
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1507.01767

arxiv created 2016/04/22 · arxiv updated 2016/04/25

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

Related

• Faster Algorithms for Largest Empty Rectangles and Boxes
• Efficiently Enumerating Scaled Copies of Point Set Patterns
• A Practical Algorithm for Enumerating Collinear Points
• Efficient Planarity Testing
• Searching edges in the overlap of two plane graphs