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


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