You are here

Forbidden Configurations in Discrete Geometry

David Epstein, University of California, Irvine
Wednesday, April 25, 2018 - 3:30pm
PDL C-401

We review and classify problems in discrete geometry that depend only on the order-type or configuration of a set of points, and that can be characterized by a family of forbidden configuations. These include the happy ending problem, no-three-in-line problem, and orchard-planting problem from classical discrete geometry, as well as Harborth's conjecture on integer edge lengths and the construction of universal point sets in graph drawing. We investigate which of these properties have characterizations involving a finite number of forbidden subconfigurations, and the implications of these characterizations for the computational complexity of these problems.

Event Type: