Name
Abstract | ||
|---|---|---|
For a point set P on the plane, a four element subset S ¿ P is called a 4-hole of P if the convex hull of S is a quadrilateral and contains no point of P in its interior. Let R be a point set on the plane. We say that a point set B covers all the 4-holes of R if any 4-hole of R contains an element of B in its interior. We show that if |R|¿ 2|B| + 5 then B cannot cover all the 4-holes of R. A similar result is shown for a point set R in convex position. We also show a point set R for which any point set B that covers all the 4-holes of R has approximately 2|R| points. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00373-007-0717-0 | Graphs and Combinatorics |
Keywords | Field | DocType |
convex position,bicolored point set,convex hull,covering,k-hole,convex quadrilaterals,point sets,similar result,point set r,element subset,set cover | Topology,Combinatorics,Convex hull,Convex set,Regular polygon,Quadrilateral,Point set,Convex position,Mathematics,Point set triangulation | Journal |
Volume | Issue | ISSN |
23 | 1 | 1435-5914 |
Citations | PageRank | References |
8 | 0.62 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshinori Sakai | 1 | 54 | 9.64 |
| Jorge Urrutia | 2 | 1064 | 134.74 |