@article {38527,
title = {Testing simple polygons},
journal = {Computational GeometryComputational Geometry},
volume = {8},
year = {1997},
type = {10.1016/S0925-7721(96)00015-6},
abstract = {We consider the problem of verifying a simple polygon in the plane using {\textquotedblleft}test points{\textquotedblright}. A test point is a geometric probe that takes as input a point in Euclidean space, and returns {\textquotedblleft}+{\textquotedblright} if the point is inside the object being probed or {\textquotedblleft}-{\textquotedblright} if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that 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 discuss extensions of our results to higher dimensions.},
keywords = {probing, Testing, Verifying},
isbn = {0925-7721},
author = {Arkin, Esther M. and Belleville, Patrice and Mitchell, Joseph S. B. and Mount, Dave and Romanik, Kathleen and Salzberg, Steven and Souvaine, Diane}
}