ICS Theory Group

ICS 269, Winter 2002: Theory Seminar


8 March 2002:
A presentation of results from "Moving an Angle Around a Region" by Frank Hoffman, Christian Icking, Rolf Klein, and Klaus Kriegel, in Proc SWAT '98, Springer Lecture Notes in Computer Science, Stockholm, 1998, and online publication by the Journal of Discrete & Computational Geometry
Javid Hüseynov

Let D be a connected region inside a simple polygon P. Authors define the angle hull, AH(D), of D to be the set of all points in P that can see two points of D at a right angle. They further prove that the perimeter AH(D) is at most twice the perimeter of the relative convex hull of D. In special case, when P is the full plane, this bound is given as {/pi}/2. Both bounds are tight.

The practical application of this topic is found in designing on-line competitive navigation strategies for autonomous robots in unknown environments.