The floodlight problem

被引：20

作者：

Bose, P

Guibas, L

Lubiw, A

Overmars, M

Souvaine, D

Urrutia, J

机构：

[1] MCGILL UNIV,DEPT COMP SCI,MONTREAL,PQ H3A 2A7,CANADA

[2] STANFORD UNIV,DEPT COMP SCI,PALO ALTO,CA 94305

[3] UNIV WATERLOO,DEPT COMP SCI,WATERLOO,ON N2L 3G1,CANADA

[4] UNIV UTRECHT,DEPT COMP SCI,NL-3508 TB UTRECHT,NETHERLANDS

[5] RUTGERS STATE UNIV,DEPT COMP SCI,NEW BRUNSWICK,NJ 08903

[6] UNIV OTTAWA,DEPT COMP SCI,OTTAWA,ON K1N 5N5,CANADA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1997年 / 7卷 / 1-2期

关键词：

illumination problems; dissecting point sets;

D O I：

10.1142/S0218195997000090

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given three angles summing to 2 pi, given n points in the plane and a tripartition k(1) + k(2) + k(3) = n, we can tripartition the plane into three wedges of the given angles 80 that the i-th wedge contains k(i) of the points. This new result on dissecting point sets is used to prove that lights of specified angles not exceeding pi can be placed at n fixed points in the plane to illuminate the entire plans if and only if the angles sum to st least 2 pi. We give O(n log n) algorithms for both these problems.

引用

页码：153 / 163

页数：11

共 13 条

[1]

[Anonymous], 1987, ART GALLERY THEOREMS

[2]

BLUM M, 1972, J COMPUT SYST SCI, V7, P448

[3] ILLUMINATING RECTANGLES AND TRIANGLES IN THE PLANE [J].

CZYZOWICZ, J ;

RIVERACAMPO, E ;

URRUTIA, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 57 (01) :1-17

[4]

CZYZOWICZ J, 1993, P 5 CAN C COMP GEOM, P393

[5]

CZYZOWICZ J, 1989, LECT NOTES COMPUTER, V382

[6]

Edelsbrunner H., 1987, ALGORITHMS COMBINATO

[7]

PACH J, 1992, COMMUNICATION

[8]

Preparata F., 2012, Computational geometry: an introduction

[9]

ROTE G, 1993, COMMUNICATION

[10] RECENT RESULTS IN ART GALLERIES [J].

SHERMER, TC .

PROCEEDINGS OF THE IEEE, 1992, 80 (09) :1384-1399

← 1 2 →