Area-Optimal Simple Polygonization Problems - Benchmark Instances, by N. Ramos, P. J. de Rezende and C. C. de Souza
Citing this page:
-
Use the BibTeX entry:
@Misc{opt-area-instances-page,
author = {Natanael Ramos and Pedro J. de Rezende and Cid C. de Souza},
title = {Area-Optimal Simple Polygonization Problems},
year = {2021},
note = {{\sl www.ic.unicamp.br/\textasciitilde cid/Problem-instances/Area-Optimal-Simple-Poly}}
}
Problem description
Problems regarding the construction of geometric objects from a set of points in the plane are often studied in Computational Geometry, including triangulations of point sets, Voronoi diagrams, arrangements, etc. Naturally, one type of objects that can be constructed from a set of points are polygons. In this vein, we have optimal polygonizations: given a set of points \(S\) in the plane, we wish to find a simple polygon \(P\), with vertex set \(S\), which optimizes a given function. In particular, one may be interested in maximizing or minimizing the area of the resulting polygon, which gives rise to the Max-Area and Min-Area problems, respectively. These problems appear in areas such as Pattern Recognition, Image Reconstruction and Clustering [1]. The pictures below show an example of optimal solutions to Min-Area and Max-Area, respectively, for the same set of 10 points. One can see that, although the solutions to both problems must obey the same structure definitions, the optimal polygons differ due to the diverse objectives. Nonetheless, regarding complexity, both problems are NP-complete [2].Min-Area Solution.
Max-Area Solution.
Input Instances
The instances are organized in compressed files, being each file named after the set that they come from: FHKPS from Fekete et. al. [3]* and GEN, a set of uniformly random instances generated by us, using the same generator employed for the CGSHOP 2019 contest. The main goal of this competition was to solve both Min-Area and Max-Area.File Format: Instances
Each instance consists of a set of \(n\) points, with \(n\) lines in the following format: <\(\ell\;x\;y\)> Each line is a description of point with coordinates \((x,y)\) and label \(\ell\). In the case of the GEN, there are also comment lines starting with a "#" character. The comments include a brief description of the instance, along with the seed used to generate it.FHKPS | instances-FHKPS.tar.gz | |
GEN | instances-GEN.tar.gz |
Results
The results were obtained with an implementation in C++ and compiled with GCC 7.5.0. We solved the ILP models with CPLEX version 12.9. To perform geometric computations, we employed the CGAL Library, version 4.13. Below you can find the machine specifications for each set of instances.Instances | CPU | #cores | Clock | Cache | RAM |
---|---|---|---|---|---|
FHKPS | Intel(R) Xeon(R) E5-2630 v4 | 10 | 2.2 GHz | 25 MB | 64 GB |
GEN | Intel(R) Core(TM) i7-3770 | 4 | 3.9 GHz | 8 MB | 32 GB |
FHKPS-I-MI | FHKPS-I-MI-results.csv | |
FHKPS-I-MA | FHKPS-I-MA-results.csv | |
GEN-I | GEN-I-results.csv |
Solution Files
For each instance, there is a corresponding solution file. Each file gives the sequence of points of the polygonization, with one point label per line.FHKPS | FHKPS-I-solutions.tar.gz | |
GEN | GEN-I-solutions.tar.gz |
Acknowledgments
*We wish to thank Michael Perk and Dr. S. P. Fekete for kindly provide the set of instances FHKPS.This work was supported in part by grants from: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (Capes), Brazil -- Finance Code 001, #88882.329122/2019-01; Brazilian National Council for Scientific and Technological Development (CNPq), Brazil, #140300/2020-1, #313329/2020-6, #309627/2017-6, #304727/2014-8; #313329/2020-6; São Paulo Research Foundation (Fapesp), Brazil, #2020/09691-0, #2018/26434-0, #2014/12236-1 and Fund for Support to Teaching, Research and Outreach Activities (Faepex).
References
- [1] S. P. Fekete, On simple polygonalizations with optimal area, Discrete & Computational Geometry 23 (2000) 73–110.
- [2] S. P. Fekete, W. R. Pulleyblank, Area optimization of simple polygons, in: C. Yap (Ed.), Proceedings of the Ninth Annual Symposium on Computational Geometry, ACM, 1993, pp. 173–182. doi:10.1145/160985.161016.
- [3] S. P. Fekete, A. Haas, P. Keldenich, M. Perk, A. Schmidt, Computing area-optimal simple polygonalizations, in: 36th European Workshop on Computational Geometry (EuroCG), 2020, pp. 20:1–20:8.
Address
Natanael Ramos, Cid C. de Souza and Pedro J. de RezendeUniversidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: