Polygonal path simplification with angle constraints (Q2571211)

The authors consider simplification problems in \(\mathbb R^2\) and \(\mathbb R^3\) for paths that have angle constraints. The resulting geometric algorithms run times that are nearly a linear factor better than graph-theoretic solutions that are based on known techniques; this leads to algorithms that match the running times for unconstrained problems. A key step in the solutions, the authors formulate and solve an offline ball exclusion search problem, which may be of interest in its own right.