Space-Efficient Geometric Divide-and-Conquer Algorithms ⋆ Prosenjit Bose a Anil Maheshwari a

We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multi-dimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer. Specifically, we present a deterministic algorithm running in O(n log n) time using O(1) extra memory given inputs of size n for the closest pair problem and a randomized solution running in O(n log n) expected time and using O(1) extra space for the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in O(n log n + k) time using O(1) extra space where n is the number of horizontal and vertical line segments and k is the number of intersections.