20070801
Spaceefficient geometric divideandconquer algorithms
Publication
Publication
Computational Geometry , Volume 37  Issue 3 SPEC. ISS. p. 209 227
We develop a number of spaceefficient tools including an approach to simulate divideandconquer spaceefficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multidimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divideandconquer. Specifically, we present a deterministic algorithm running in O(nlogn) time using O(1) extra memory given inputs of size n for the closest pair problem and a randomized solution running in O(nlogn) 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(nlogn+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.
Additional Metadata  

In situ algorithms, Inplace algorithms, Spaceefficient algorithms  
dx.doi.org/10.1016/j.comgeo.2006.03.006  
Computational Geometry  
Organisation  Computational Geometry Lab 
Bose, P, Maheshwari, A, Morin, P, Morrison, J. (Jason), Smid, M, & Vahrenhold, J. (Jan). (2007). Spaceefficient geometric divideandconquer algorithms. In Computational Geometry (Vol. 37, pp. 209–227). doi:10.1016/j.comgeo.2006.03.006
