# CG:SHOP 2020

Download## Minimum Convex Partition Problem

We are happy to announce the CG Challenge 2020, as part of CG Week in Zurich, Switzerland, June 22-26, 2020. As in the CG Challenge 2019, the objective will be to compute good solutions to instances of a difficult geometric optimization problem.

The contributors with the best solutions will be recognized at CG Week and invited to present their results. In addition, the top contributing teams will be invited to submit an extended abstract describing their methods and results, to be included in the LIPIcs proceedings of SoCG.### Description

The specific problem chosen for the 2020 Challenge is the following:
Given a set *S* of *n* points in the plane. The objective is to compute a plane graph with vertex set *S* (with each point in *S* having positive degree) that partitions the convex hull of *S* into the smallest possible number of convex faces.
(Note that collinear points are allowed on face boundaries, so all internal angles of a face are at most *π*.)

The complexity of this problem is still unknown, but approximation algorithms have been proposed; e.g., see Christian Knauer and Andreas Spillner: Approximation Algorithms for the Minimum Convex Partition Problem, SWAT 2006, pp. 232-241.

### Important Dates

**Contest opens:**18:00 CEDT (noon, EDT), September 30, 2019.

**Contest closes:**24:00 (midnight, AoE), February 14, 2020.

**Invitations for proceedings contributions:**February 21, 2020.

**Final versions of proceedings contributions due:**March 31, 2020.

### Instances

The contest starts with a total of 247 instances, as follows.Each instance consists of n points in the plane with even integer coordinates.

For n={10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000}, there are six instances each.

In addition, there is one instance of size n=1000000.

These instances are of three different types:

**uniform:**uniformly at random from a square

**edge:**randomly generated according to the distribution of the rate of change (the "edges") of an image

**illumination:**randomly generated according to the distribution of brightness of an image (such as an illumination map)

### Access

Instances can be downloaded above. This is also the site for submitting solutions. Participation requires registering on the website; please follow the instructions. Participation is possible as an individual or as a team.### Evaluation

The contest will be based on the following objective:** Minimize the total score over all instances.**

*f*of convex faces of a partition of the set

*P*of

*n*points in the plane,

*c*of which lie on the convex hull of

*P*, the score is f/(2n-c-2), i.e., the ratio between the achieved partition value and the value of a triangulation.

The total score is the sum of all individual instance scores.

Participation requires submitting feasible solutions. Feasibility will be checked at the time of upload; failing the feasibility test or submitting no solution for an instance results in a default score of 1 for this instance.

### Categories

The contest will be run in an**Open Class**, in which participants may use any computing device, any amount of computing time (within the duration of the contest) and any team composition.

In addition, organizers may announce specific rules for two further classes.

In the

**Limited Class**, produced code will be run on a standardized machine with limited runtime.

In the

**Junior Class**, a team must consist exclusively of participants who are eligible according to the rules of CG:YRF, defined as not having defended a formal doctorate before 2018.

Please watch this space and further announcements and specifications.

Additional categories (such as honorary mentions for best solutions to specific instances, different subsets of the instances (e.g. small or large), or particularly elegant solutions) may be named at the discretion of the organizers. Tiebreaker: In case of ties, the tiebreaker will be the time a specific score was obtained. (Participants are encouraged to submit early and often.)

### Submission format:

See the separate descripton.

Erik Demaine, Sándor Fekete, Phillip Keldenich, Dominik Krupke, Joe Mitchell

### Instance Files

In the context of this contest, an instances is a set of points in the Euclidean plane.
These points have integer coordinates between -2^{40} and 2^{40},
which implies that IEEE double precision floating point numbers can represent coordinates without loss of precision.

Our instances are available as a ZIP archive. For each instance, this archive contains a JSON (JavaScript Object Notation) file. The JSON format is a well-known, wide-spread format; there are JSON parser libraries for nearly all practically relevant programming languages. If you find integrating a JSON parser into your project too cumbersome, we provide a Python-based utility library containing an instance reader that you can use to transform the instance into a simpler format of your choice.

In this JSON format, an instance may look like this:

{ "points": [ {"i": 0, "x": -2396.0, "y": -5284.0}, {"i": 1, "x": 2656.0, "y": 2938.0}, {"i": 2, "x": 4120.0, "y": 2278.0}, {"i": 3, "x": 4342.0, "y": 102.0}, {"i": 4, "x": 4384.0, "y": 2988.0}, {"i": 5, "x": 5136.0, "y": 2280.0}, {"i": 6, "x": 6634.0, "y": 5416.0}, {"i": 7, "x": 8598.0, "y": 2632.0}, {"i": 8, "x": 8898.0, "y": 4170.0}, {"i": 9, "x": 11738.0, "y": 1550.0} ], "type": "Instance", "name": "example-0000010", "meta": { "comment": "HIP even point set instance (10 points) sampled from image", "faces_in_triangulation": 12 } }

Each instance JSON file contains exactly one object.
That object contains at least a list of points called `points`

, a `name`

that is unique to the instance and an attribute `type`

which is set to `Instance`

, stating that this object actually encodes an instance.
It may also contain a `meta`

attribute, containing additional meta information, such as a comment, and the number of faces in a triangulation of the point set.
Each entry in the list `points`

is an object containing the three attributes `i`

, `x`

and `y`

.
`x`

and `y`

are the point's coordinates as IEEE double precision floating point values.
`i`

is the point index, an integer ranging from 0 to n-1, where n is the number of points in the instance.
Each point is uniquely identified by its index.
Moreover, there are no duplicate points in our instances; however, there are instances with collinear points, i.e., more than two points on a line.

### Solution Files

In the context of this contest, a solution to an instance is a set of edges, i.e., pairs of vertex indices corresponding to the index `i`

specified in the `points`

list of the instance.
The solution for an instance must satisfy the following conditions.

- No edge is a loop that connects a vertex to itself.
- Each vertex is incident to at least two edges.
- No edge intersects another edge in its interior.
- No point lies in the interior of an edge.
- The boundary of the convex hull of the points is covered (exactly) by a subset of output edges
- The finite faces of the arrangement induced by the edges are convex.

For this contest, you may upload your solutions as ZIP archives containing solutions files. Analogously to instance files, solutions are encoded in JSON; a solution may look as follows.

{ "type": "Solution", "instance_name": "triangle-0000003", "meta": { "comment": "My Awesome Solver generated this solution!" }, "edges": [ {"i": 0, "j": 1}, {"i": 1, "j": 2}, {"i", 2, "j", 0} ] }

Similar to JSON parsers, there are JSON generators for virtually all practically relevant programming languages.
If you generate solution files ad-hoc, remember that the attribute names in JSON, unlike in JavaScript, must be enclosed in quotation marks.
A solution must have a `type`

attribute set to `Solution`

.
Moreover, it must an attribute `instance_name`

corresponding to the unique name given by the `name`

attribute of the corresponding instance.
Furthermore, the list of edges contained in the solution must be given as the `edges`

attribute of the solution.
Each edge is an object containing two attributes `i`

and `j`

indicating the indices of the points connected by the edge.
Finally, a solution may contain a `meta`

attribute containing metadata or a comment.
You may combine several solutions in a single JSON file containing a list of solutions.