Tentative Prune-and-Search for Computing Fixed-Points with Applications to Geometric Computation

ID
TR-93-30
Authors
D. Kirkpatrick and J. Snoeyink
Publishing date
October 1993
Length
16 pages
Abstract

Motivated by problems in computational geometry, we investigate the complexity of finding a fixed-point of the composition of two or three continuous functions that are defined piecewise. We show that certain cases require nested binary search taking Theta(log^2(n)) time. Others 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.