CG:SHOP 2023

Minimum Coverage by Convex Polygons

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, \ldots, 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 .) 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

You can find the instances for the competition here. See also Instance Format for more information.

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