Technical Reports

The ICICS/CS Reading Room

UBC CS TR-93-30 Summary

Tentative Prune- and- Search Fixed-Points with Applications to Geometric Computation, October 1993 D. Kirkpatrick and J. Snoeyink, 16 pages

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

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.

If you have any questions or comments regarding this page please send mail to