ICS Theory Group

ICS 269, Spring 2004: Theory Seminar

11 June 2004:

Today we will have two speakers.

Jeremy Yu Meng
Computing the Visibility Graph of Points Within a Polygon

This is a presentation of the paper "Computing the Visibility Graph of Points Within a Polygon," by Boaz Ben-Moshe, Olaf Hall-Holt, and Matthew J. Katz, and Joseph Mitchell, SCG 2004.

Abstract: The authors study the problem of computing the visibility graph defined by a set P of n points inside a polygon Q: two points p,q in P are joined by an edge if the segment pq is contained in Q.

Kevin Wortman
On finding a guard that sees most and a shop that sells most

This is a presentation of the paper "On Finding a Guard That Sees Most and a Shop That Sells Most," by Otfried Cheong, Alon Efrat, and Sariel Har-Peled, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms.

Abstract: We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time.

Due to time constraints I will be focusing on a few select results of the paper.