Raising roofs crashing cycles and playing pool: Applications of a data structure for finding pairwise interactions
| Author(s) : | Jeff Erickson, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | The straight skeleton of a polygon is a variant of the medial axis, introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We construct the straight skeleton of an n-gon with r reflex vertices in time O(n, |