Polygonal path simplification with angle constraints

摘要

We present efficient geometric algorithms for simplifying polygonal paths in R 2 and R 3 that have angle constraints, improving by nearly a linear factor over the graph-theoretic solutions based on known techniques. The algorithms we present match the time bounds for their unconstrained counterparts. As a key step in our solutions, we formulate and solve an off-line ball exclusion search problem, which may be of interest in its own right. (c) 2004 Elsevier B.V. All rights reserved.