Computational Geometry:
Solving Hard Optimization Problems
(CG:SHOP @ SoCG2019)
Geometric Optimization Challenge 2019

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

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

Click here to see format information. Download instances
Submit Solutions