Space-efficient geometric divide-andconquer algorithms

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 solutions running in O(n logn) time using O(1) extra memory given inputs of size n for the closest pair problem and the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in O(n logn + 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.