This paper presents a framework for reasoning about robust geoemtric algorithms. Robustness is formally defined and a data structure called an approximate polygon is introduced and used to reason about polygons constructed of edges whose positions are uncertain.
A robust algorithm for point location in an approximate polygon is presented. The algorithm uses only the signature of the point (not its location) to determine whether the point is inside or outside the polygon.
An approximate polygon could, by shifting its edges back and forth within their error bounds, induce a large number of different line arrangements. The cell C_alpha with signature "alpha" in one such arrangment will be different than the cell C'_alpha with signature "alpha" in another arrangement. This paper proves that, regardless of their positions and shapes, the cells C_alpha and C'_alpha are always to the same side of the polygons which induce their respective arrangements.
Conference version (extended abstract): 39 Kb compressed Postscript file
Full version (technical report): 62 Kb compressed Postscript file .
@inproceedings{Stewart-cccg91,
author = "A. James Stewart",
title = "Robust point location in approximate polygons (extended abstract)",
booktitle = "Canadian Conference on Computational Geometry",
year = "1991",
month = "August",
pages = "179--182"
}
@techreport{Stewart-tr91,
author = "A. James Stewart",
title = "Robust point location in approximate polygons",
institution = "Cornell University Computer Science Department",
year = "1991",
type = "technical report",
number = "91--1208"
}