Accession Number:

ADA123335

Title:

How to Divide a Polygon Fairly

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1982-04-01

Pagination or Media Count:

25.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE