We are happy to announce the Fifth Computational Geometry Challenge,
as part of CG Week in Dallas, TX, USA, June 12-15, 2023.
As in previous years, the objective will be to compute good solutions
to instances of a difficult geometric optimization problem.
The specific problem chosen for the 2023 Challenge is
Minimum Coverage by Convex Polygons, as follows.
Description
Given a geometric region, P, in the plane, which may be
a simple polygon or a polygon with holes.
The task is to cover P with a collection, C_1,…, C_k,
of convex polygons, each contained within P.
Objective
Minimize k, the number of convex polygons in the cover.
Motivation
Optimal coverage problems have an extensive history in
Computational Geometry. In fact, the well-known SoCG logo
shows that an optimal solution to the Minimum Cover by rectangles
may include (rotated) rectangles whose vertices are not among those of the
input polygon P, even in the case that P is an orthogonal simple polygon.
(See reference [1] and https://www.computational-geometry.org/logo.html <https://www.computational-geometry.org/logo.html>.)
It is also relevant in practical contexts, such as surveillance and robot navigation.
The Minimum Cover by Convex Polygons problem is not only NP-hard [2],
but was recently shown to be ∃R-complete [3], which most likely implies
that it is not in the class NP.
Details of the competition (such as benchmark instances, data formats,
and rules for submission and evaluation) will be announced in the coming
weeks. Appropriate steps will be undertaken (e.g., by restricting the
classes of feasible subsets) to ensure straightforward, automated
verification of solutions.
The contributors with the most outstanding solutions will be recognized
at CG Week 2023 and invited to present their results, both at the event
and in the proceedings.
We are looking forward to your contributions and welcome questions
and comments!
Instances
A large number and variety of input polygonal regions P will be
provided for the competition. These will be released at a later time.
(See below.)
Credit
This problem was suggested by Dan Halperin, Tel Aviv University.
References
[1] Joseph O'Rourke. "The complexity of computing
minimum convex covers for polygons,"
Proc. 20th Allerton Conf. Commun. Control Comput., 1982, pp. 75-84.
(See https://www.computational-geometry.org/logo.html <https://www.computational-geometry.org/logo.html>)
[2] Joseph C. Culberson and Robert A. Reckhow.
"Covering polygons is hard". Journal of Algorithms 17.1 (1994), pp. 2–44.
[3] Mikkel Abrahamsen. Covering polygons is even harder.
FOCS 2021: 375-386.
Challenge Team
Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra
Advisory Board
Bill Cook, Andreas Fabri, Dan Halperin, Michael Kerber,
Philipp Kindermann, Joe Mitchell, Kevin Verbeek
Timeline
A first batch of test instances will be released in late September 2022;
the actual benchmark instances for the Challenge will be released
in October. The contest will close in early 2023.
• First test instances: September 30, 2022
• Contest instances: October 28, 2022
• Contest Closes: January 27, 2023
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
