# 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.