| [home] - [up] |
Abstract: In the minimum weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We prove that the decision version of this problem is NP-hard. We use a reduction from a PLANAR-1-IN-3-SAT, a special variation of the satisfiability problem.
The correct working of the gadgets is established with computer assistance, using geometric inclusion and exclusion criteria for MWT edges, such as the diamond test and the LMT-Skeleton heuristic, as well as dynamic programming on polygonal faces.
Joint work with Wolfgang Mulzer.
Colloquium - 16:00
Abstract: Given a set of curves in the plane or a topological graph, we ask for an orientation of the curves or edges which induces an acyclic orientation on the corresponding planar map. Depending on the maximum number of crossings on a curve or an edge, we provide algorithms and hardness proofs for this problem.
Joint work with Eyal Ackerman, Christian Knauer and Günter Rote.