ICS Theory Group

CompSci 269S, Winter 2008: Theory Seminar

June 6, 2008, 1:00pm in Bren Hall 1423

A Randomized Algorithm for Constructing the Trapezoidal Map Induced by a Connected Geometric Graph

Darren Strash


We discuss the general problem of constructing the trapezoidal map induced by a set of line segments in the plane, and present preliminary results for a randomized algorithm for the special case when the line segments form a connected geometric graph.

This is joint work with Michael Goodrich.