Minimum Convex Partition of Point Sets - Benchmark Instances and Solutions, by A. S. Barboza, C. C. de Souza and P. J. de Rezende

Citing this page:

@Misc{mcpp-instances-page, author = {Allan S. Barboza and Cid C. de Souza and Pedro J. de Rezende}, title = {Minimum Convex Partition of Point Sets - Benchmark Instances and Solutions}, year = {2018}, url = {www.ic.unicamp.br/~cid/Problem-instances/Convex-Partition} }

Problem description

Let

P

$P$ be a set of

n

$n$ points in the plane in general position, i.e., with no three collinear points. We say that a simple polygon is empty w.r.t.

P

$P$ if it contains no points of

P

$P$ in its interior. Denote by

H (P)

$H(P)$ the convex hull of

P

$P$ . A convex partition (also called decomposition) of

P

$P$ is a planar subdivision of the convex hull of

P

$P$ into nonoverlapping empty convex polygons whose vertices are the points of

P

$P$ . The Minimum Convex Partition Problem (MCPP) asks to find a convex partition of

P

$P$ that minimizes the number of faces.

The pictures below show an example of an instance with of the MCPP (a), its convex hull (b), a suboptimal convex partition (c), and an optimal convex partition (d).

(a) An instance $P$ of the MCPP with $n = 8$ points

(b) Convex Hull $H(P)$

(d) An optimal convex partition of $P$

Input Instances

The instances of this benchmark are organized in compressed files, divided into two sets: T1, and T2. The set T1 contains instances of sizes 30 to 50 for which optimal solutions were found by the method described in [1]. known. Set T2 contains instances of sizes 55 to 110.

All instances were generated by chosing points in a unitary square, no three points being colinear. Each instance was given a name according to the following pattern:

RNDS-< $n$ >-<id>.inst

$n$ : Number of vertices, or size.
$id$ : Identication distinguishing instances of the same size.

Instance Files

Each instance consists of a set of points, in the following format:

n

$n$ >
<

x y

$x\;y$ >

The value

n

$n$ is the number of points. The remaining

n

$n$ lines have two rational numbers

x y

$x y$ corresponding to the horizontal and vertical coordinates, respectively, of each point. Rationals are given in the format

p / q

$p/q$ , where

p

$p$ and

q

$q$ are integers, and

q \neq 0

$q ≠ 0$ .

	T1	instances-T1.tar.gz (278K)
	T2	instances-T2.tar.gz (478K)

Results

The results are given in csv files, each one corresponding to one of the sets of instances solved by a given method. In one of these files, each row corresponds to the result of one instance. The columns in the file are the name of the instance and its size, followed by different data, such as running time and best solution found. Each data column contains the name of its configuration and/or algorithm.

Edge-based Model

These results are for the edge based model presented in [1]. These solutions were obtained with an implementation of heuristics in C++, compiled with GCC compiler version 7.2.0, using -O3 as optimization level. As an ILP solver, we employed IBM's ILOG CPLEX version 12.8.0.
Geometric structures and procedures were implemented using CGAL 4.2-5, using exact rational numbers represented by Gmpq. All algorithms ran in single-thread mode. We conducted the experiments on a computer with an Intel® Xeon® CPU E5-2420 processor at 1.90 GHz and 32GB of RAM.

Each CPLEX run was limited to 20 minutes.

	T1	results-T1.csv (25K)
	T2	results-T2.csv (20K)

Polygon-based Model

These results are for the polygon based model presented in [2]. These solutions were obtained with an implementation of the heuristics in C++, compiled with the GCC compiler version 7.2.0, using -O3 as optimization level. As an ILP solver, we employed SCIP 7.0 as ILP solving, using IBM's ILOG CPLEX version 12.10 as the LP solver.
Geometric structures and procedures were implemented using CGAL 5.1, using exact rational numbers represented by Gmpq. All algorithms ran in single-thread mode. We conducted the experiments on a computer with an Intel® Xeon® CPU Silver 4114 processor at 2.2 GHz and 32GB of RAM.

Each SCIP run was limited to 3 hours, exclusing preprocessing and model generation.

	T2 (only from 65 to 105 points)	results-fullsp.csv (30K)
	T2 (only from 65 to 105 points)	results-cgsp.csv (32K)

Solution Files

For each instance, there is a corresponding solution file. The name of the file follows this pattern:

RNDS-< $n$ >-<id>-<solver>.sol

The content of each solution file is in the following format:

m f

$m f$ >
<

u v 1

$u\ v\ 1$ >

where

m

$m$ is the number of edges and

f

$f$ is the number of internal (convex) faces. The subsequent

m

$m$ lines contain a pair of integers

u v

$u\ v$ per line describing the vertices of each edge, where

u

$u$ and

v

$v$ are the

u

$u$ -th and

v

$v$ -th points in the order of appearance in the corresponding instance file.

Edge-based Model [1]

	T1	solutions-T1.tar.gz (250K)
	T2	solutions-T2.tar.gz (384K)

Polygon-based Model [2]

	T2 (only from 65 to 105 points)	solutions-fullsp.tar.xz (118K)
	T2 (only from 65 to 105 points)	solutions-cgsp.tar.xz (87K)

Acknowledgments

This research was supported by grants from Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) #304727/2014-8, #304727/2014-8, #311140/2014-9, #309627/2017-6, #313329/2020-6; from Coordenação de Aperfeiçoamento de Pessoal de Ensino Superior (Capes) #1738500 and from Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) #2014/12236-1, #2017/12523-9, #2018/26434-0, #2020/09691-0.

References

[1] Minimum Convex Partition of Point Sets, A. S. Barboza, C. C. de Souza & P. J. de Rezende, In Algorithms and Complexity – 11-th International Conference, CIAC 2019, (pages 25–37). Springer, 2019.
[2] Solving the Minimum Convex Partition of Point Sets with Integer Programming, A. Sapucaia, P. J. de Rezende, & C. C. de Souza, submitted for publication (2020).

Address

Allan Sapucaia, Cid C. de Souza and Pedro J. de Rezende
Institute of Computing
University of Campinas
Av. Albert Einstein, 1251
13083-852 Campinas, SP, Brazil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail:

Instituto de Computação - UNICAMP