Protecting convex sets |
| |
Authors: | Jurek Czyzowicz Eduardo Rivera-Campo Jorge Urrutia Joseph Zaks |
| |
Affiliation: | 1. Département d’Informatique, Université du Québec à Hull, Hull, C.P. 1250, Suce, J8X 3X7, Québec, Canada 2. Departamento de Matemáticas, Universidad Autónoma Metropolitana-Iztapalapa, 09340, Mexico D.F., Mexico 3. Department of Computer Science, University of Ottawa, K1N 9B4, Ottawa, Ontario, Canada 4. Department of Mathematics, University of Haifa, 31905, Haifa, Israel
|
| |
Abstract: | ![]() A point-setS is protecting a collection F =T 1,T 2,..., n ofn mutually disjoint compact sets if each one of the setsT i is visible from at least one point inS; thus, for every setT i ∈F there are points xS andy T i such that the line segment joining x to y does not intersect any element inF other thanT i . In this paper we prove that [2(n-2)/3] points are always sufficient and occasionally necessary to protect any family F ofn mutually disjoint compact convex sets. For an isothetic family F, consisting ofn mutually disjoint rectangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary to protect it. IfF is a family of triangles, [4n/7] points are always sufficient. To protect families ofn homothetic triangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|