How to Divide a Polygon Fairly
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Lipton and Tarjans planar separator theorem LT77, L177 is notable example of a systematic technique for introducing a computational tool, i.e., divide-and-conquer, into a whole class of relate problems, i.e., planar graph problems. Drawing its inspiration from this philosophy, this paper presents a theoretical result on polygon decomposition which can be applied to derive a number of efficient algorithms for geometric problems, in particular, problems of convex decompositions, triangulation, visibility, and internal distance.
- Theoretical Mathematics