Paper Details

[ Downloads: 0 | Abstract Viewed: 1094 | Pages: 4 ]

Abstract of the Article

Note: English CIVILICA is in its Trial Period so Full Texts can not be provided! Persian users can download it here

Path Simplification under Difference Area Measure

Authors:
[ Shervin Daneshpajouh ] - Department of Computer Enginering, Sharif University of Technology, Tehran, Iran
[ Alireza Zarei ] - Department of Computer Enginering, Sharif University of Technology, Tehran, Iran
[ Mohammad Ghodsi ] - Sharif University of Technology Computer Engineering Department & School of Computer Science Institue for Research in Fundamental Science (IPM), Tehran, Iran

Abstract:

In this paper , we consider path simplification problem under difference area ( diff-area ) measure , Diff- area measure is defined as [AA(Q)-AB(Q)] is the area under Q and above P and AB(Q) is the area above Q and under P (see Figure 1 ) . Bose et al . [1] presented an approximation algorithm for finding a simplified path with at most K vertices that minimizes the diff - area measure whch only works on x - monotone paths . The constraint of being , - monotone is restrictive in some applications like tracking bird migration paths or map boundary simplification . Here , we extend the method of Bose et al . [1] and present algorithms with the same time complxities as theirs for general paths.

Keywords: