ICS Theory Group

ICS 269, Winter 1996: Theory Seminar

8 March 1996:
Fairly Recent Results about Triangulations
Brad Hutchings, ICS, UC Irvine

Brad will discuss two fairly recent results about triangulations. The first result is the Subgraph Theorem from "A Quadratic Time Algorithm for the MinMax Triangulation" by Edelsbrunner and Tan [SIAM J. Comput., vol. 22, 1993, pp. 527-551]. The second result is an improved beta for the beta-skeleton subgraph of the minimum weight triangulation. This result appeared in the paper "A better subgraph of the minimum weight triangulation" by Yang [IPL, vol. 56, 1995, pp. 255-258].

During his talk, Brad will be using his new graph algorithm visualization application to compute and display results from these papers on random graphs.