On the Area Bisectors of a Polygon

被引：18

作者：

K. -F. Böhringer

B. R. Donald

D. Halperin

机构：

[1] Department of Electrical Engineering,

[2] University of Washington,undefined

[3] Box 352500,undefined

[4] Seattle,undefined

[5] WA 98195-2500,undefined

[6] USA karl@ee.washington.edu,undefined

[7] www.ee.washington.edu/faculty/karl ,undefined

[8] Department of Computer Science,undefined

[9] Dartmouth College,undefined

[10] 6211 Sudikoff Laboratory,undefined

[11] Hanover,undefined

[12] NH 03755-3510,undefined

[13] USA brd@cs.dartmouth.edu,undefined

[14] www.cs.dartmouth.edu/ {}brd ,undefined

[15] Department of Computer Science,undefined

[16] Tel Aviv University,undefined

[17] Tel Aviv 69978,undefined

[18] Israel halperin@math.tau.ac.il,undefined

[19] www.math.tau.ac.il/ {}halperin,undefined

来源：

Discrete & Computational Geometry | 1999年 / 22卷 / 2期

关键词：

Explicit Representation; Distinct Area; Simple Polygon; Algebraic Characterization;

D O I：

10.1007/PL00009460

中图分类号：

学科分类号：

摘要：

We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatoriallydistinct if they induce different partitionings of the vertices of P . We derive an algebraic characterization of area bisectors. We then show that there are simple polygons with n vertices that have Ω(n2) combinatorially distinct area bisectors (matching the obvious upper bound), and present an output-sensitive algorithm for computing an explicit representation of all the bisectors of a given polygon.

引用

页码：269 / 285

页数：16