TENTATIVE PRUNE-AND-SEARCH FOR COMPUTING FIXED-POINTS WITH APPLICATIONS TO GEOMETRIC COMPUTATION

Article type: Research Article

Authors: Kirkpatrick, David | Snoeyink, Jack

Affiliations: Department of Computer Science, University of British Columbia, 201-2366 Main Mall, Vancouver, BC V6T 1Z4 Canada

Abstract: Motivated by problems in computational geometry, this paper investigates the complexity of finding a fixed-point of the composition of two or three continuous functions that are defined piecewise. It shows that certain cases require nested binary search taking Θ(log2 n) time. Other cases can be solved in logarithmic time by using a prune-and-search technique that may make tentative discards and later revoke or certify them. This work finds application in optimal subroutines that compute approximations to convex polygons, dense packings, and Voronoi vertices for Euclidean and polygonal distance functions.

DOI: 10.3233/FI-1995-2243

Journal: Fundamenta Informaticae, vol. 22, no. 4, pp. 353-370, 1995