# CG:SHOP 2020

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

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 |

### 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_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`

.

### Upload

Put all solution files into a zip. Our verifier will search all non-hidden folders for json files. Do not include any other files as it would bloat the zip and possibly confuse the verifier. We recommend to use our Python3 module cgshop2020_pyutils.