research-article

An Empirical Study on Randomized Optimal Area Polygonization of Planar Point Sets

Authors:

Jiju Peethambaran,

Amal Dev Parakkat,

Ramanathan MuthuganapathyAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 21

Article No.: 1.10, Pages 1 - 24

https://doi.org/10.1145/2896849

Published: 22 April 2016 Publication History

Abstract

While random polygon generation from a set of planar points has been widely investigated in the literature, very few works address the construction of a simple polygon with minimum area (MINAP) or maximum area (MAXAP) from a set of fixed planar points. Currently, no deterministic algorithms are available to compute MINAP/MAXAP, as the problems have been shown to be NP-complete. In this article, we present a greedy heuristic for computing the approximate MINAP of any given planar point set using the technique of randomized incremental construction. For a given point set of n points, the proposed algorithm takes O(n²log n) time and O(n) space. It is rather simplistic in nature, hence very easy for implementation and maintenance. We report on various experimental studies on the behavior of a randomized heuristic on different point set instances. Test data have been taken from the SPAETH cluster data base and TSPLIB library. Experimental results indicate that the proposed algorithm outperforms its counterparts for generating a tighter upper bound on the optimal minimum area polygon for large-sized point sets.

References

[1]

Thomas Auer and Martin Held. 1998. RPG—heuristics for the generation of random polygons. In Proceedings of the 8th Canadian Conference on Computational Geometry. 38--44.

Digital Library

[2]

Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. 2008. Computational Geometry: Algorithms and Applications (3rd ed.). Springer-Verlag TELOS, Santa Clara, CA.

Digital Library

[3]

James E. Boyce, David P. Dobkin, Robert L. (Scot) Drysdale III, and Leo J. Guibas. 1985. Finding extremal polygons. SIAM Journal on Computing 14, 1, 134--147.

Digital Library

[4]

Linda Denee. 1988. Polygonizations of point sets in the plane. Discrete and Computational Geometry 3, 1, 77--87.

Digital Library

[5]

David Eppstein, Mark Overmars, Günter Rote, and Gerhard Woeginger. 1992. Finding minimum area k-gons. Discrete and Computational Geometry 7, 45--58.

Digital Library

[6]

Sándor P. Fekete. 1992. Geometry and the Travelling Salesman Problem. Ph.D. Thesis. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON.

[7]

S. P. Fekete. 2000. On simple polygonalizations with optimal area. Discrete & Computational Geometry 23, 1, 73--110.

[8]

Sanchit Goyal. 2010. A survey on travelling salesman problem. Midwest Instruction and Computing Symposium. 1--9.

[9]

V. Muravitskiy and V. Tereshchenko. 2011. Generating a simple polygonalization. In Proceedings of the 15th International Conference on Information Visualisation (IV’11). IEEE Computer Society, Washington, DC, 502--506.

Digital Library

[10]

Joseph O’Rourke. 1998. Computational Geometry in C (2nd ed.). Cambridge University Press, New York, NY.

Digital Library

[11]

Jiju Peethambaran, Amal Dev Parakkat, and Ramanathan Muthuganapathy. 2015. A randomized approach to volume constrained polyhedronization problem. Journal of Computing and Information Science in Engineering 15, 1.

[12]

Gerhard Reinelt. 2014. TSPLIB database. Retrieved March 27, 2016 from http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

[13]

Micha Sharir, Adam Sheffer, and Emo Welzl. 2011. Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn’s technique. CoRR abs/1109.5596.

[14]

Helmuth Spaeth. 2014. SPAETH Cluster Analysis Datasets. Retrieved March 27, 2016 from http://people.sc.fsu.edu/&sim;jburkardt/datasets/spaeth/spaeth.html.

[15]

Maria Teresa Taranilla, Edilma Olinda Gagliardi, and Gregario Hernandez Penalver. 2011. Approaching minimum area polygonization. In XVII Congreso Argentino de Ciencias de la Computacin.

[16]

Remco C. Veltkamp. 1995. Boundaries through scattered points of unknown density. Graphic Models and Image Processing 57, 6, 441--452.

Digital Library

[17]

Chong Zhu, Gopalakrishnan Sundaram, Jack Snoeyink, and Joseph S. B. Mitchell. 1996. Generating random polygons with given vertices. Computational Geometry 6, 5, 277--290.

Digital Library

Cited By

Demaine EFekete SKeldenich PKrupke DMitchell J(2022)Area-Optimal Simple Polygonalizations: The CG Challenge 2019ACM Journal of Experimental Algorithmics10.1145/350400027(1-12)Online publication date: 4-Mar-2022
https://dl.acm.org/doi/10.1145/3504000
Crombez Lda Fonseca GGerard Y(2022)Greedy and Local Search Heuristics to Build Area-Optimal PolygonsACM Journal of Experimental Algorithmics10.1145/350399927(1-11)Online publication date: 17-Mar-2022
https://dl.acm.org/doi/10.1145/3503999
Fekete SHaas AKeldenich PPerk MSchmidt A(2022)Computing Area-Optimal Simple PolygonizationsACM Journal of Experimental Algorithmics10.1145/350360727(1-23)Online publication date: 25-May-2022
https://dl.acm.org/doi/10.1145/3503607
Show More Cited By

Index Terms

An Empirical Study on Randomized Optimal Area Polygonization of Planar Point Sets
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Empty pseudo-triangles in point sets

We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies ...
On finding an empty staircase polygon of largest area (width) in a planar point-set

This paper presents an algorithm for identifying a maximal empty-staircase-polygon (MESP) of largest area, among a set of n points on a rectangular floor. A staircase polygon is an isothetic polygon bounded by two monotonically rising (falling) ...
Generating a Simple Polygonalizations
IV '11: Proceedings of the 2011 15th International Conference on Information Visualisation

We consider the methods of construction simple polygons for a set S of n points and applying them for searching the minimal area polygon. In this paper we propose the approximate algorithm, which generates the simple polygonalizations of a fixed point ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 21, Issue

Special Issue SEA 2014, Regular Papers and Special Issue ALENEX 2013

2016

404 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/2888418

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 April 2016

Accepted: 01 February 2016

Revised: 01 October 2015

Received: 01 August 2012

Published in JEA Volume 21

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
184
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Demaine EFekete SKeldenich PKrupke DMitchell J(2022)Area-Optimal Simple Polygonalizations: The CG Challenge 2019ACM Journal of Experimental Algorithmics10.1145/350400027(1-12)Online publication date: 4-Mar-2022
https://dl.acm.org/doi/10.1145/3504000
Crombez Lda Fonseca GGerard Y(2022)Greedy and Local Search Heuristics to Build Area-Optimal PolygonsACM Journal of Experimental Algorithmics10.1145/350399927(1-11)Online publication date: 17-Mar-2022
https://dl.acm.org/doi/10.1145/3503999
Fekete SHaas AKeldenich PPerk MSchmidt A(2022)Computing Area-Optimal Simple PolygonizationsACM Journal of Experimental Algorithmics10.1145/350360727(1-23)Online publication date: 25-May-2022
https://dl.acm.org/doi/10.1145/3503607
Kovalchuk MTereshchenko VTereshchenko Y(2022)Optimization of Algorithms for Simple PolygonizationsCommunication and Intelligent Systems10.1007/978-981-19-2130-8_47(603-617)Online publication date: 19-Aug-2022
https://doi.org/10.1007/978-981-19-2130-8_47
Cicerone SD'Emidio MDi Stefano GNavarra A(2021)On the effectiveness of the genetic paradigm for polygonizationInformation Processing Letters10.1016/j.ipl.2021.106134171(106134)Online publication date: Oct-2021
https://doi.org/10.1016/j.ipl.2021.106134
Yang KNam KQutbuddin AReich AHuhn V(2021)Size constrained k simple polygonsGeoinformatica10.1007/s10707-020-00416-925:1(43-67)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s10707-020-00416-9
Asaeedi SDidehvar FMohades A(2018)NLP Formulation for Polygon Optimization ProblemsMathematics10.3390/math70100247:1(24)Online publication date: 27-Dec-2018
https://doi.org/10.3390/math7010024
Reich AOhriniuc RYang KBanaei-Kashani FHoel EGüting RTamassia RXiong L(2018)Size constrained k simple polygonsProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274962(500-503)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3274895.3274962

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents