The objective is to compute good solutions for instances of
a challenging geometric optimization problem. The contributors
with the most outstanding solutions are recognized at CG Week
and invited to present their results, both at the event and in the
proceedings.
Previous problems were as follows:
- Finding a simple polygon with minimum area (Challenge 2019)
- Finding a subdivision with few convex pieces (Challenge 2020)
- Coordinating the motion of a large set of objects (Challenge 2021)
- Partitioning a set of edges into few plane subgraphs (Challenge 2022)
- Minimum coverage by convex polygons (Challenge 2023)
- Maximum polygon packing (Challenge 2024)
- Minimum Non-Obtuse Triangulations (Challenge 2025)
See https://cgshop.ibr.cs.tu-bs.de for details.
To broaden the scope of Challenge problems and ensure
sufficient diversity, we are soliciting suitable problems for
the Eigth CG Challenge, to be part of CG Week 2026.
Desirable properties are as follows.
- The problem is of geometric nature.
- The problem is of general scientific interest and has
received previous attention.
- Optimization problems tend to be more suitable than
feasibility problems; suggestions for feasibility problems
are also possible, provided they come with sufficiently
fine-grained scoring.
- Computing optimal solutions is difficult for instances of
reasonable size.
- This difficulty is of a fundamental algorithmic nature,
and not only due to issues of encoding or access to
sophisticated software or hardware.
- Verifying feasibility of provided solutions is relatively easy.
To nominate a problem, please send the following by
May 20 by email:
- An informal description of the problem
- A pointer to previous work, if any
- Further useful information on the state of practical solutions, if any
- Contact information of the nominator
Nominators may be contacted for further details; they may
also be invited to participate in running the challenge.
The selected problem will be announced in June, 2025.
We are looking forward to your contributions and welcome
questions and comments!
Challenge Team and Advisory Board:
--------------------------------------------------
Bill Cook, Andreas Fabri, Sándor Fekete, Dan Halperin,
Phillip Keldenich, Michael Kerber, Philipp Kindermann,
Dominik Krupke, Joe Mitchell, Stefan Schirra, Kevin Verbeek
**********************************************************
*
* 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
