Speaker: Michael Khanimov (TAU)

Title: Delaunay triangulations of degenerate point sets

Abstract:
---------
The Delaunay triangulation (DT) is one of the most common and useful triangulations of
point sets P in the plane. DT is not unique when P is degenerate, specifically 
when it contains quadruples of co-circular points. One way to achieve uniqueness 
is by perturbing P.

We try to figure out how a specific perturbation of such degenerate sets
affects their DTs. We focus on two special configurations, where (1) the points of P
form a uniform grid, and (2) the points of P are vertices of a regular polygon.

The talk presents many interesting (and sometimes surprising) empirical findings 
and properties of the perturbed DT's for these cases, and gives theoretical 
explanations to some of them.

Joint work with Micha Sharir.