DIMACS TR: 93-14
Testing Simple Polygons
Authors: Esther M. Arkin, Patrice Belleville, Joseph S.B.Mitchell,
David Mount, Kathleen Romanik, Steven Salzberg, Diane L. Souvaine
ABSTRACT
We consider the problem of verifying a simple polygon in the plane
using test points. A test point is a geometric probe that takes
as input a point in Euclidean space, and returns "+" if the point is
inside the object being probed or "-" if it is outside. We give a
procedure for verifying an n-sided, non-degenerate, simple polygon
using 5n test points. This testing strategy works even if the test
polygon has n+1 vertices. We also give algorithms using O(n) test
points for simple polygons which may be degenerate and for test
polygons that may have up to n+2 vertices. All of these algorithms
work for polygons with holes. We also give an extension of the basic
testing algorithm to d dimensions.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-14.ps
DIMACS Home Page