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

The results are in csv files, each one corresponding to one of the set of instances. Each row of each file corresponds do the result of one instance. The columns in the file indicate the name of the instance, the primal/dual bounds and the computation time used to find such bounds.

In the case of the GEN-I instances, the columns have a suffix _\(k\) where \(k\) is the model version's identifier.
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 Rezende
Universidade 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: