How to Divide a Polygon Fairly

Abstract

Lipton and Tarjan's 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1982
Accession Number
ADA123335

Entities

People

  • Bernard Chazelle

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Decomposition
  • Geometry
  • Lists (Data Structures)
  • Numerical Analysis
  • Pattern Recognition
  • Polygons
  • Preprocessing
  • Separators
  • Theorems
  • Triangles
  • Triangulation

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design