# CG:SHOP 2020

Organized by: Erik Demaine (MIT), Sándor Fekete (TU Braunschweig), Phillip Keldenich (TU Braunschweig), Dominik Krupke (TU Braunschweig), Joseph S. B. Mitchell (Stony Brook University)
25 teams participating
Sept. 30, 2019, 4 p.m. (UTC) - Feb. 15, 2020, 11:59 a.m. (UTC)

## 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 $$\pi$$.

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 integer coordinates.
For $n \in \{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$$.

On January, 21st, we added an additional set of 99 instances of a different type to allow a better distinction between the different solvers.

Info: We announced 100 new instances but it is actually only 99, increasing the number of instances to 346.

The instances are of four 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)
• orthogonally collinear points: randomly generated on an integral grid to have a lot of collinear points (similar to PCBs and distorted blueprints).

Organizers may add further instances at a later time in order to allow additional evaluations.

### 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:

Maximize the total score over all instances.

For each instance, the score is a number between 0 and 1, with higher scores corresponding to better solutions. The trivial solution, i.e., a triangulation, corresponds to a score of 0, and a solution without any edges, which is of course infeasible, corresponds to a score of 1.

For an instance, i.e., a point set $$P$$ consisting of $$n$$ points, let $$c$$ be the number of points on the convex hull of $$P$$. Observe that any triangulation of $$P$$ is a convex partition with $$2n - 2 - c$$ bounded faces and $$3(n-1)-c$$ edges. Moreover, any convex partition $$\Pi$$ can be obtained by starting with a triangulation containing its edges, and removing the excess edges one by one. In this process, removing a single edge also decreases the number of bounded faces by exactly 1. Thus, any solution $$\Pi$$ with $$f = 2n - 2 - c - s$$ faces for some $$s \geq 0$$ has $$m = 3(n-1)-c-s$$ edges and vice versa. This allows us to use the number $$m(\Pi)$$ of edges in a solution $$\Pi$$ instead of the number of faces to determine the score of $$\Pi$$ as $\text{score}(\Pi) := \frac{s(\Pi)}{3(n-1)-c}\text{, where } s(\Pi) = 3(n-1) - c -m(\Pi).$ In other words, the score for a solution to an instance $$P$$ is the fraction of edges removed from a triangulation of $$P$$.

The total score is the sum of all individual instance scores; only the best feasible solution submitted is used to compute the score. Participation requires submitting feasible solutions. Feasibility is checked at the time of upload. Failing to submit a feasible solution for an instance results in a default score of 0 for that instance.

Tiebreaker: In case of ties, the tiebreaker will be the time a specific score was obtained. Participants are encouraged to submit early and often.

### 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.

#### Limited Class

Info: After evaluating the feedback we received and gauging the effort required for setting up another, special server to run the solvers on, we have come to the conclusion that we will not offer a Limited Class for this challenge.

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.

#### Junior Class

To be eligible to participate 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.

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.

### Submission format

See the separate description.

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

##### Top Teams

The following table shows the scores of the best teams with the number of instances for which they achieved a solution that was not beaten by any other team (best solutions), as well as the number of solutions where they beat all other teams (unique best solutions). Teams that have enabled the Incognito-Mode will not appear here.

Rank Team Score # Best solutions # Unique best solutions
1 Team UBC 175.17288027836375 209 11
2 OMEGA 175.1305970705367 297 126
3 CGA-Sbg 175.04020666564546 187 0
4 Les Shadoks 174.69558640363132 160 6
5 G-SCOP 174.5430683157742 138 0
6 Min2Win@Zurich 174.3847842613453 121 0
7 Team Technion 173.97371586645923 100 0
8 TUFUnky4you 173.6218569292868 99 0
9 Sapucaia, de Rezende, de Souza 170.93957370799882 88 0
10 ucsbtheorylab 169.97517963220014 76 0
11 eigen 169.49947521274578 94 0
12 geo-ET 164.8120798620325 66 0
13 Mystic Heuristic 163.86525889401867 71 0
14 Fast & Greedious 161.90446012395728 18 0
15 fu-berlin 156.19967413358435 17 0
16 cr1degun 153.12994096177226 25 0
17 GeometricAlgoTeam 149.64447952672265 4 0
18 Xmarksthespot 96.79079997803501 2 0
19 UniWue 76.87388342454577 0 0
20 2IMA15 Group 12 49.16168273497199 0 0
21 Tübingen Bus 0.5857142857142857 2 0

##### Score Plot

Evaluate the progress of your team(s), we provide a score over time.

##### Solution Status

See the value of your best solutions.

### 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 -240 and 240, 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_delaunay": 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. Give the file the extension .solution.json.