Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-167-88
Visibility and Intersection Problems in Plane Geometry
Authors: Chazelle, Bernard, Guibas, Leonidas J.
Date:June 1988
Pages:39
Download Formats:
Abstract:
We develop new data structures for solving various visibility and intersection problems about a simple polygon P on n vertices. Among our results are a simple O(n log n) time algorithm for computing the illuminated subpolygon of P from a luminous side, and an O(log n) time algorithm for determining which side of P is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing on P which takes time O(n log n) and space O(n). The two main tools in attacking these problems are geometric duality on the two-sided plane and fractional cascading.