Place the Vertices Anywhere on the Curve and Simplify

• Autorzy: Rudi Ali Gholami

Identyfikatory

DOI

10.3233/FI-2021-2041

• Języki publikacji: EN

Abstrakty

EN

A polygonal curve is simplified to reduce its number of vertices, while maintaining similarity to its original shape. Numerous results have been published for vertex-restricted simplification, in which the vertices of the simplified curve are a subset of the vertices of the input curve. In curve-restricted simplification, i.e. when the vertices of the simplified curve are allowed to be placed on the edges of the input curve, the number of vertices may be much more reduced. In this paper, we present algorithms for computing curve-restricted simplifications of polygonal curves under the local Hausdorff distance measure.

Słowa kluczowe

EN

curve simplification; geometric algorithms; computational geometry

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 3
• Strony: 275--287
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Rudi Ali Gholami

• Department of Electrical and Computer Engineering, Babol Noshirvani University of Technology, Babol, Mazandaran, Iran

Bibliografia

• [1] Imai H, Iri M. Polygonal approximations of a curve - formulations and algorithms. In: Toussaint GT (ed.), Computational Morphology: A computational Geometric Approach to the Analysis of Form, pp. 71-86. North-Holland, 1988. doi:10.1016/S0734-189X(86)80027-5.
• [2] Agarwal PK, Har-Peled S, Mustafa NH, Wang Y. Near-Linear Time Approximation Algorithms for Curve Simplification. Algorithmica, 2005. 42(3-4):203-219. doi:10.1007/S00453-005-1165-Y.
• [3] Zhang D, Ding M, Yang D, Liu Y, Fan J, Shen HT. Trajectory Simplification - An Experimental Study and Quality Analysis. Proceedings of the VLDB Endowment, 2018. 11(9):934-946. doi:10.14778/3213880.3213885.
• [4] Buzer L. Optimal simplification of polygonal chain for rendering. In: Symposium on Computational Geometry (SoCG). 2007 pp. 168-174. doi:10.1145/1247069.1247102.
• [5] van de Kerkhof M, Kostitsyna I, Löffler M, Mirzanezhad M, Wenk C. Global Curve Simplification. In: European Symposium on Algorithms (ESA). 2019 pp. 67:1-67:14. doi:10.4230/LIPICS.ESA.2019.67.
• [6] Douglas DH, Peucker TK. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica, 1973. 10(2):112-122.
• [7] Hershberger J, Snoeyink J. An O(n log n) implementation of the Douglas-Peucker algorithm for line simplification. In: Annual ACM Symposium on Computational Geometry (SoCG). ACM, 1994 pp. 383-384. doi:10.1145/177424.178097.
• [8] Hershberger J, Snoeyink J. Cartographic Line Simplification and Polygon CSG Formulae and in O(n log*n) Time. In: International Workshop on Algorithms and Data Structures. Springer, 1997 pp. 93-103. doi:10.1007/3-540-63307-3_50.
• [9] Chan WS, Chin F. Approximation of polygonal curves with minimum number of line segments or minimum error. International Journal of Computational Geometry & Applications, 1996. 6(1):59-77. doi:10.1142/S0218195996000058.
• [10] Melkman A, O’Rourke J. On polygonal chain approximation. In: Toussaint GT (ed.), Computational Morphology: A Computational Geometric Approach to the Analysis of Form, pp. 87-95. North-Holland, 1988.
• [11] Chen DZ, Daescu O. Space-Efficient Algorithms for Approximating Polygonal Curves in Two-Dimensional Space. International Journal of Computational Geometry & Applications, 2003. 13(2):95-111. doi:10.1142/S0218195903001086.
• [12] Abam MA, de Berg M, Hachenberger P, Zarei A. Streaming Algorithms for Line Simplification. Discrete & Computational Geometry, 2010. 43(3):497-515. doi:10.1007/S00454-008-9132-4.
• [13] Lin X, Ma S, Zhang H, Wo T, Huai J. One-Pass Error Bounded Trajectory Simplification. PVLDB, 2017. 10(7):841-852. doi:10.14778/3067421.3067432.
• [14] Cao W, Li Y. DOTS - An online and near-optimal trajectory simplification algorithm. Journal of Systems and Software, 2017. 126:34-44. doi:10.1016/J.JSS.2017.01.003.
• [15] Muckell J, Olsen PW, Hwang JH, Lawson CT, Ravi SS. Compression of trajectory data - a comprehensive evaluation and new approach. GeoInformatica, 2017. 18(3):435-460. doi:10.1007/S10707-013-0184-0.
• [16] van Kreveld MJ, Löffler M, Wiratma L. On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance. In: Symposium on Computational Geometry (SoCG). 2018 pp. 56:1-56:14. doi:10.4230/LIPICS.SOCG.2018.56.
• [17] Bringmann K, Chaudhury BR. Polyline Simplification has Cubic Complexity. In: Symposium on Computational Geometry (SoCG). 2019 pp. 18:1-18:16. doi:10.4230/LIPICS.SOCG.2019.18.
• [18] de Berg M, Cheong O, van Kreveld MJ, Overmars MH. Computational geometry - algorithms and applications. Springer, third edition, 2008. doi:10.1007/978-3-540-77974-2.
• [19] Guibas LJ, Hershberger J, Mitchell JSB, Snoeyink J. Approximating Polygons and Subdivisions with Minimum Link Paths. International Journal of Computational Geometry & Applications, 1993. 3(4):383-415. doi:10.1142/S0218195993000257.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).