Computational Geometry: Solving Hard Optimization Problems (CG:SHOP)

Open Problems and Hard Instance Challenges Workshop

CG Week (June 17-21, 2019), Portland, OR

Open problems have driven much of the research pursuits in computational geometry, computational topology, and all of mathematics and computer science. Pursuit of well-publicized open problems have motivated significant advances, particularly in theoretical pursuits, for which the metrics for success are clear. Equally important, practically important challenges in solving hard instances of problems have led to advances in combinatorial optimization.

This workshop seeks to provide resources to the community to assist in collecting, organizing and tracking progress on open problems posed in all areas of computational geometry and topology. In addition, through an optimization challenge targeting a hard geometric optimization problem, the workshop seeks to promote creative solutions of practical importance; this may also attract attention and interest from outside the classic computational community.

Organizers: Erik Demaine (MIT), Sándor Fekete (TU Braunschweig), Joseph S. B. Mitchell (Stony Brook University)

Call for Open Problems in CG/CT

This is an open call for researchers to pose and present, in a very brief and precise format, open problems from any area of CG/CT. Presenters are to give brief background and motivation, precise statement of the open problem, and its status. Presentations of contributed open problems will be limited to a few minutes during the workshop. All contributed problems will be collected and made available to CG Week participants.

In order to allow sufficient time for collecting and preloading presentations, contributions are encouraged by June 11, 2019. Please use the Open Problem Submission site. Additionally, there will be an option to pose impromptu problems at the workshop.

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

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.

For the collection of benchmark instances of the problem, of various sizes n, a description of data formats, metrics for success, and detailed instructions on how to upload solutions see the following website: http://cgshop.ibr.cs.tu-bs.de

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.

Workshop Schedule (one afternoon, 3-4 hours)

Introduction [the organizers]: Overview, summary of background on the The Open Problems Project (TOPP), updates (TOPP 2.0), and the role of open problems in driving research in CG/CT
Contributed open problems

[Break]

Hard Instances Challenge overview, and presentation of prizes [the organizers]
Presentation by winner(s) of the challenge
Wrap-up and summary; benchmarks, contest repositories, Hard Instances Project (HIP); future directions discussion [moderated by the organizers]