首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Protecting convex sets
Authors:Jurek Czyzowicz  Eduardo Rivera-Campo  Jorge Urrutia  Joseph Zaks
Institution: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号