Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

A time-optimal Delaunay refinement algorithm in two dimensions

 

Alper Ungor
Assistant Professor
Computer & Inf. Science & Eng.
University of Florida, Gainesville, FL

Delaunay triangulations find great use in many fields, including engineering simulations, graphics, visualizations, robotics, geographic information systems, and biological modeling. Triangulations (meshes) are often required to have bounded aspect-ratio (quality guarantee) and small number of elements. Delaunay refinement is a popular method to compute such meshes. The original Delaunay refinement algorithm had quadratic time complexity in terms of the size of output.
I will present a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes O(n log n + m) time, where n is the input size and m is the minimum size of a good quality mesh. This is the first time-optimal Delaunay refinement algorithm.
I will also present experimental results showing that our algorithm performs better than the previous Delaunay refinement algorithms not only in theory but also in practice.
The talk is based on a joint work with Sariel Har-Peled which appeared in Proc. of ACM-SoCG 2005.

 

DATE: July 29, 2005, Friday @ 14:00
PLACE: EA 409