Illuminating high-dimensional convex sets |
| |
| Authors: | Jurek Czyzowicz Bruno Gaujal Eduardo Rivera-Campo Jorge Urrutia Joseph Zaks |
| |
| Affiliation: | (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-spaceEdis said toilluminate a familyF={S1, ...,Sn} ofn disjoint compact sets inEdif for every setSiinF and every pointx in the boundary ofSithere 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={S1, ...,Sn} ofn disjoint compact sets inEd. 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 等数据库收录！ |
|
