# CG:SHOP 2019

Organized by: Erik Demaine (MIT), Sándor Fekete (TU Braunschweig), Joseph S. B. Mitchell (Stony Brook University)
Feb. 28, 2019, midnight (UTC) - May 31, 2019, midnight (UTC)

## Overview

This year's optimization challenge problem is the problem Optimal Area Polygonalization: Given a set S of n points in the plane, compute a simple polygonalization of S (a simple polygon whose vertex set is precisely the set S) that has maximum or minimum area among all polygonalizations of S. (Every set S of n points in the plane has at least one polygonalization. The number of different polygonalizations is finite (though possibly exponentially large) for any finite points set S.) The optimization problems, both for maximization or for minimization, are known to be NP-hard; see S. P. Fekete, On Simple Polygonalizations with Optimal Area, Discrete and Computational Geometry 23:73-110 (2000). Thus, the Challenge encourages implementations of solutions that are based on heuristics, on methods of combinatorial optimization, guided search, etc.

A collection of benchmark instances of the problem, of various sizes n, will be made available via this website, by about February 28, 2019. Solutions should be uploaded to a link that will be provided, linked from this website. Precise examples of data files for submission will also be provided at this website.

The Challenge is open to all. There is no requirement that participants be registrants at CG Week 2019; however, outstanding solutions will be recognized at the Workshop and at least one winning participant/team will be invited to present their results and methods at the Workshop.

Submissions to the Challenge need not include solutions to all provided instances; one can submit solutions to any subset of the instances, and they can be for either the area maximization or the area minimization problem, or both.

Solutions will be checked for correctness (that each ordered list of points of S is a valid polygonalization) and for value (the area of the corresponding polygon). We also solicit work on lower bounds for minimization and upper bounds for maximization; further details on this part will be provided at the time of the release of instances. There is no intention to evaluate solutions/software for speed of computation. Submissions can be based on implementations of heuristics, exhaustive search, applied combinatorial optimization, or anything else.

One or more participants/teams that submit solutions will be recognized for being outstanding, based on the solution values.

## Details

Contest opens 24:00 (midnight, CET), February 28, 2019.
Contest closes 24:00 (midnight, CET), May 31, 2019.

The objective is to compute good solutions to instances of an NP-hard geometric optimization problem, as follows.

#### Minimum (Maximum) Area Polygon

Given: A set S of n points in the plane
Wanted: A simple polygon P whose vertex set is precisely the set S, such the the area of P is as small (large) as possible.
The contest consists of a total of 247 instances, as follows. 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 will be 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)
Each instance consists of n points in the plane with even integer coordinates. (This ensures that the area of any simple polygon will be an integer.)

Instances can be downloaded below. 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.

The contest will be run in several different categories. These categories include:

• (Score_min) The best total score for minimum area polygons
• (Score_max) The best total score for maximum area polygons
• (Opt_min) The largest number of instances solved to optimality for a minimum area polygon
• (Opt_max) The largest number of instances solved to optimality for a maximum area polygon
• (Bound_min) The best bounds for minimization
• (Bound_max) The best bounds for maximization

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.

For each instance, the score is the ratio between the achieved area, divided by the area of the convex hull, i.e., a number between 0 and 1. For instances without a feasible solution, the default score is 1 (for minimization) or 0 (for maximization). The total score is the sum of all 247 individual scores.

#### Score contest:

Participation requires submitting feasible solutions. Feasibility will be checked at the time of upload; failing the feasibility test results in a default score.

#### Optimality contest:

It lies in the nature of NP-hardness that proving optimality for a solution may be tedious, and verifying such a claim may be tricky; at the same time, this difficulty makes work on establishing optimal solutions particularly interesting. As a consequence, verifying the optimality of a submitted solution may require direct interaction between the organizing committee and the participants, as follows.

Participation in an optimality contest requires a feasible solution, along with a brief description of how it was obtained. Participants should be prepared to respond to questioning of optimality, which may include demonstrating their solution method, logs with time stamps, etc. Submitting claims of optimality without any means to back up such a claim is strongly discouraged; clearly, ethical standards for academic honesty apply.

#### Bound contest:

Just like in the optimality contest, participation in a bound contest requires a set of valid lower (for minimization) or upper (for maximization) bounds, along with a brief description of how they were obtained. Participants should be prepared to respond to questioning of their bounds, which may include demonstrating their validity. Due to the difficulty of verifying bounds, the bound contest will have to rely on the discretion of the organizers; depending on the submissions, solutions may be evaluated according to total score and/or their simplicity.

(The organizers will provide updates as the contest develops.)

#### Tiebreaker:

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

### Instance Files

An instance has the format:

# file: my_instance.instance
# Empty lines and lines that begin with # are ignored
# index x y
0   0   0
1   2   0
2   2   2
3   0   2


### Solution Files

A solution should have the same base name as the instance and the extension .solution. It should list the indices in the order the tour uses it. You can use a middle part such as instance_name.middlepart.solution to make the names unique without additional folders. If you don't use a middle part, only use one dot. Names with double dots will be rejected.

# file: my_instance.123.solution <- Not needed
# You can write some personal comments here like used parameters etc.
# index <- Not needed
3
2
1
0

A solution that claims to achieve the minimum or maximum area should have the extension .minopt_solution or .maxopt_solution, respectively. This will automatically create and enter the corresponding bounds file (described next).

### Bound Files

Files that contain bounds should have the extension .min_bound for the minimum area polygons or .max_bound for maximum area polygons. The description of your argument, why there cannot be polygon with a smaller (min_bound) or larger (max_bound) area, should be written as comments (lines starting with #). You only have to give us an idea of what you did (e.g., "derived by CPLEX...") but we might ask you to deliver the details later for verification. There should be a single line containing the value of the bound.

# file: my_instance.123.min_bound
# Description
# ...
# ...
32.1

The last read bound will overwrite previously submitted bounds (if the value changes). This also means, that you should always only submit your best bound (but you can describe further bounds in the corresponding description).
If your previous bound was erroneous, simply submit an empty bound to delete the old bound.