On Realistic Line Simplication under Area Measure
Shervin Daneshpajouh, Alireza Zarei, Mohammad Ghodsi · 2009
In this paper, we consider the well-known 2D line simplication problem under area measure. Primarily, we propose a unied denition for the area measure that can be used on a general path of n vertices. We present an O(n 3 ) optimal simplication algorithm on general paths under unied area mea- sure based on Imai and Iri's approach. Next, to im- prove the time complexity, we describe a realistic sit- uation in which the path lies inside a bounded re- gion. For such a realistic input path, we propose an -approximate algorithm of O( n 2 ) time complexity to nd the simplication. We further dene a variant of the area measure that overcomes the pitfalls of the common area measure arisen in degenerated cases. Our optimal or approximation algorithms can employ this measure at the same time and space complexities. Although, the area is the rst natural simplication measure, to the best of our knowledge, the results pre- sented here are the rst sub-cubic simplication algo- rithms on this measure for general paths. Keywords: Computational geometry, line simplic ation, line gen- eralization, area measure, approximation algorithm.