OOSTRUM , René Van

A polyhedral terrain is the image of a piecewise linear continuous function de ned over the triangles of a triangulation in the xy- plane. Given a terrain with n vertices, two simply-connected regions (subsets of the triangles), and any constant e > 0, we an determine in O(n2+e) time and storage whether or not the two regions are completely...

Let A and B be two sets of n resp. m (m ≥ n) disjoint unit disks in the plane. We consider the problem of finding a rigid motion of A that maximizes the total area of its overlap with B. The function describing the area of overlap is quite complex, even for combinatorially equivalent translations, and hen e, we turn our attention to...

Let P be a simple polygon. We de ne a witness set W to be a set of points su h that if any (prospective) guard set G guards W, then it is guaranteed that G guards P . We show that not all polygons admit a nite witness set. If a fi nite minimal witness set exists, then it cannot contain any witness in the interior of P ; all witnesses must lie...