Towards In-place Geometric Algorithms and Data Structures

• Journal version under submission  
• Version submitted to SoCG'04  

Abstract: For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

Related publications

• Space-efficient planar convex hull algorithms , with J. Iacono, J. Katajainen, P. Morin, J. Morrison, and G. Toussaint.
• Inplace convex hull of a polygonal line in linear time, with T. Chan.