2018
Compatible 4-holes in point sets
Publication
Publication
Presented at the
30th Canadian Conference on Computational Geometry, CCCG 2018 (August 2018), Winnipeg
Counting interior-disjoint empty convex polygons in a point set is a typical Erdős-Szekeres-type problem. We study this problem for convex 4-gons. Let P be a set of n points in the plane and in general position. A subset Q of P, with four points, is called a 4-hole in P if Q is in convex position and its convex hull does not contain any point of P in its interior. Two 4-holes in P are compatible if their interiors are disjoint. We show that P contains at least ⌊5n/11⌋−1 pairwise compatible 4-holes. This improves the lower bound of 2⌊(n − 2)/5⌋ which is implied by a result of Sakai and Urrutia (2007).
| Additional Metadata | |
|---|---|
| Conference | 30th Canadian Conference on Computational Geometry, CCCG 2018 |
| Citation |
Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2018). Compatible 4-holes in point sets. In Proceedings of the 30th Canadian Conference on Computational Geometry, CCCG 2018 (pp. 346–352).
|