Illuminating high-dimensional convex sets |
| |
Authors: | Jurek Czyzowicz Bruno Gaujal Eduardo Rivera-Campo Jorge Urrutia Joseph Zaks |
| |
Institution: | (1) Dépt. d'Informatique, Université du Québec à Hull, J8X 3X7 Hull, Québec, Canada;(2) INRIA, Sophia-Antipolis, France;(3) Dept. de Matemáticas, Universidad Autonóma Metropolitana-I, 09340 México D.F., México;(4) Dept. of Computer Science, University of Ottawa, K1N 9B4 Ottawa, Ontario, Canada;(5) Dept. of Mathematics, University of Haifa, 31905 Haifa, Israel |
| |
Abstract: | A setL of points in thed-spaceE
d
is said toilluminate a familyF={S
1, ...,S
n
} ofn disjoint compact sets inE
d
if for every setS
i
inF and every pointx in the boundary ofS
i
there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S
1, ...,S
n
} ofn disjoint compact sets inE
d
. We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets. |
| |
Keywords: | 52-XX |
本文献已被 SpringerLink 等数据库收录! |
|