Abstract
In this paper, we propose modifications of some known efficient algorithms for solving the problem of MAP (finding a simple polygon of minimum area). We propose an algorithm that somewhat expands the computational capabilities of the considered algorithms and has the complexity (n2log(n)) using O(n) memory. Also, we have proposed an original postprocessing that evaluates the performance of other algorithms by optimizing the configuration of local points within the specified complexity estimate (O(n2), O(n)). Experimental results show that it is advisable to use the algorithm in combination with postprocessing taking into account time. Unless there are strict time limits, postprocessing can be useful for randomized algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Worboys MF, Duckham M (2006) Monitoring qualitative spatiotemporal change for geosensor networks. Int J Geogr Inform Sci 20(10):1087–1108
Galton A (2005) Dynamic collectives and their collective dynamics. COSIT, LNCS 3693:300–315
Miller HJ, Han J (eds) Geographic data mining and knowledge discovery. CRC Press
Galton A, Duckham M (2006) What is the region occupied by a set of points? GIScience 2006. LNCS 4197:81–98
Fekete SP (2000) On simple polygonalizations with optimal area. Discrete and computational geometry. Springer, Berlin
Velho L (1996) Simple and efficient polygonization of implicit surfaces. J Graph Tools 1(2):5–24
Zhang H, Zhao Q, Yu L, Generation of simple polygons from ordered points using an iterative insertion algorithm. https://doi.org/10.1371/journal.pone.0230342
Fekete S, Friedrichs S, Hemmer M, Papenberg M, Schmidt A, Troegel J (2015) Area- and boundary-optimal polygonalization of planar point sets. In: EuroCG 2015, Ljubljana, Slovenia, March 16–18, pp 133–136
Fekete S, Friedrichs S, Hemmer M, Papenberg M, Schmidt A, Troegel J (2020) Computing area-optimal simple polygonalizations. In: 36th European workshop on computational geometry, Würzburg, Germany, March 16–18, pp 20:1–20:8
Tereshchenko V, Muravitskiy V (2011) Constructing a simple polygonalizations. J World Acad Sci Eng Technol 77:668–671
Osiponok M, Tereshchenko V (2019) The “Divide and Conquer” technique to solve the minimum area polygonalization problem. In: 2019 IEEE international conference on advanced trends in information theory, proceedings, pp 336–339
Peethambaran J, Parakkat AD, Muthuganapathy R (2016) An empirical study on randomized optimal area polygonization of planar point sets. J Exp Algorithmics 21(1):A:1-A:25
Taranilla MT, Gagliardi EO, Peñalver GH (2011) Approaching minimum area polygonization. Universidad Nacional de La Plata, pp 161–170
Joe B, Simpson RB (1987) Corrections to lee’s visibility polygon algorithm. BIT Numer Math 27(4):458–473
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Kovalchuk, M., Tereshchenko, V., Tereshchenko, Y. (2022). Optimization of Algorithms for Simple Polygonizations. In: Sharma, H., Shrivastava, V., Kumari Bharti, K., Wang, L. (eds) Communication and Intelligent Systems . Lecture Notes in Networks and Systems, vol 461. Springer, Singapore. https://doi.org/10.1007/978-981-19-2130-8_47
Download citation
DOI: https://doi.org/10.1007/978-981-19-2130-8_47
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-2129-2
Online ISBN: 978-981-19-2130-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)