Approximate curve-restricted simplification of polygonal curves. Issue 2 (3rd April 2021)

• Record Type: Journal Article
• Authors: Rudi, Ali Gholami
• Is Part Of: International journal of computer mathematics. Volume 6:Issue 2(2021)
• Page Start: 178
• Page End: 187
• Publication Date: 2021-04-03
• Subjects: Curve simplification -- geometric algorithms -- computational geometry; 68U05 -- 52c99; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2021.1905717
• Languages: English
• ISSNs: 2379-9927

Abstract

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.