Convex Bichromatic Quadrangulation of Point Sets: Benchmark Instances by Allan Sapucaia, P. J. de Rezende and C. C. de Souza

Citing this page:

    Use the BibTeX entry:

    @Misc{cqbpsmf-instances-page,
     author = {Allan Sapucaia and     Pedro J. de Rezende and Cid C. de Souza},
     title = {Convex Bichromatic Quadrangulation of Point Sets: Benchmark Instances - Benchmark Instances},
     year = {2021},
     url = {www.ic.unicamp.br/~cid/Problem-instances/BichromaticPartition}
    }

Convex Bichromatic Quadrangulation of Point Sets with Minimum Color Flips - Problem description

A bicoloring of a point set \(P\) is a bipartition of its points. Given a point set \(P\) in the plane and a bicoloring \(C=(R,B)\), in the Convex Bichromatic Quadrangulation of Point Sets with Minimum Color Flips Problem, we wish to find an alternative bicoloring \(C'=(R',B')\) that is
(a) closest to \(C\) with respect to their symmetric difference \(R \Delta R' = B \Delta B'\), and
(b) such that \(P\) admits a bichromatic convex quadrangulation under the new coloring \(C'\), i.e., a partition of the convex hull of \(P\) into convex quadrangles where the endpoints of each edge have distinct colors in \(C'\).

This NP-hard optimization problem was first introduced in [1] and combines two decision problems from the literature: the Convex Quadrangulation Problem and the Convex Quadrangulation of Bichromatic Point Sets Problem [2].

Input Instances

The name of each instance follows the pattern:

     r<\(n\)>-<\(id\)><\(coloring\)><\(quad\)>.inst

  • \(n\): Number of points, or size.
  • id: Point set identification, between 0 and 20.
  • coloring: Coloring identification, which can be either 'a', or 'b' or 'c'.
  • quad: Indicates whether the instance admits a quadrangulation, and it can be either 't' or 'f'.

File Format: Instances
Each instance consists of a list of points, in the following format:

     <\(n\)>
     <\(x\ y\)>
     <\(c\)>

The value \(n\) is the number of points. Each of the next \(n\) lines has two rational numbers \(x\) and \(y\) corresponding to the horizontal and vertical coordinates of each point. Each of the remaining \(n\) lines contains a binary value indicating the color of each point.


 Quadrangulable instances quad.tar.xz (130k)

Non Quadrangulable instances nonquad.tar.xz (130k)

Results

The results are divided into csv files. Each row of each file corresponds to an instance. The columns in the file indicate the properties being measured and the model used. In the case of heuristics, the property is followed by the name of the heuristic. More information about these results can be found in [1].

Quadrangulable Instances Description quad-instances.csv (5.8K)

Natural Model results-natural.csv (18.6K)

Natural Model - Relaxation Support results-natural-support.csv (69.2K)

Set-Partition Model results-setpartition.csv (38.9K)

Set-Partition Model - Relaxation Support results-setpartition-support.csv (96.4K)

Heuristics results-heuristics.csv (145.8K)

These solutions were obtained with an implementation in C++14, compiled with GCC compiler version 7.2.0, using -O3 as optimization level. Integer Linear Programs and their relaxations were solved using IBM's ILOG CPLEX version 12.10.0, with default parameters.
Geometric structures and procedures were implemented using employing CGAL 5.2, exact rational numbers represented by Gmpq. We conducted the experiments on a computer with an Intel® Xeon® CPU Silver 4114 processor at 2.2 GHz with 10 cores and 32GB of RAM.

Solution Files

For each instance, and configuration, there are two corresponding solution files. In this context, configuration refers to the method, either a model or a heuristic, used to obtain it.
One describes the quadrangulation by the edges of the planar subdivision it defines. The name of the file follows the pattern:

     <inst_name>_<configuration>.sol

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

     <\(m\) \(q\)>
     <\(u_i\) \(v_i\) \(w_i\)>

where \(m\) indicates the number of edges and \(q\) the number of quadrangles. This is followed by \(m\) lines describing the edges. For each edge, \(u_i\) and \(v_i\) indicate its endpoints (indexed starting from 0). Also, (\w_i) indicates the value assigned by the solver, which assumes 0 or 1 for exact models and heuristics, and a fractional value in \([0,1]\) for relaxations.
The second solution file describes the new coloring. The name of the file is in the following pattern:

     <inst_name>_<configuration>.col

The content of each of these solution files is in the format:

     <\(n\)>
     <\(c_i\)>

where \(n\) indicates the number of points. This is followed by \(n\) lines describing the coloring. For each point \(i\), \(c_i\) indicates its color, which can be 0 or 1 for exact models and heuristics, and a fractional value in \([0,1]\) for relaxations.


Natural Model solutions-natural.tar.xz (699K)

Set-Partition Model solutions-setpartition.tar.xz (718K)

Heuristics solutions-heuristics.tar.xz (184K)

Acknowledgments

This research was supported in part by grants from: Brazilian National Council for Scientific and Technological Development (CNPq) #313329/2020-6, #309627/2017-6, #306454/2018-1; São Paulo Research Foundation (FAPESP) #2020/09691-0, #2018/ 26434-0, #2018/14883-5, #2014/12236-1.

References

  • [1] Convex Bichromatic Quadrangulation of Point Sets with Minimum Color Flips , A. Sapucaia, A. A. Cire, P. J. de Rezende, & C. C. de Souza, submitted for publication (2021).
  • [2] Convex Quadrangulations of Bichromatic Point Sets, A. Pilz & C. Seara , In International Journal on Computational Geometry and Applications 29 (pages 289–299), 2019.

Address

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