Approximate curve-restricted simplification of polygonal curves

Abstract

The goal in the min-# curve simplification problem is to reduce the number of vertices of a polygonal curve without changing its shape significantly. Usually the vertices of the simplified curve are required to be a subset of the vertices of the input curve. We study the case in which new vertices can be placed on the edges of the input curve, and the set of vertices of the simplified curve appear in order along the input curve. If error is defined as the maximum distance between corresponding sub-curves of the input and simplified curves, we present an approximation algorithm for curves in the plane that computes a curve whose number of links is at most twice the minimum possible.

Keywords:

• Curve simplification
• geometric algorithms
• computational geometry

2010 Mathematics Subject Classifications:

• 68U05
• 52c99

Disclosure statement

No potential conflict of interest was reported by the author(s).