IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Sun, 20 Apr 2014 08:31:51

Lingas, A. (1985). On Partitioning Polygons. Technical Report LiTH-IDA-R-85-13, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the 1st ACM Symposium on Computational Geometry, Baltimore, Maryland, June 5-7, 1985. (bibtex),

Abstract: Chazelle has shown how to partition any simple polygon P into two polygons, each of total weight not greater than two thirds of the total weight of P, by drawing a diagonal within P. Under the assumption that a triangulation of P is given, we provide a straightforward proof of Chazelles theorem and derive generalizations of the theorem to include polygons with polygonal holes. The generalizations are main results of the paper.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>