On convex holes in d-dimensional point sets

2020/07/17 by Bukh, Boris, Ting-Wei Chao, Chao, Ting-Wei +2
Computer Science · Mathematics · #11K38 #52C10 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.2007.08972

openalex publication_date 2020/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a finite set A ⊆ ℝ^d, points a₁,a₂,\dotsc,a_ℓ ∈ A form an ℓ-hole in A if they are the vertices of a convex polytope which contains no points of A in its interior. We construct arbitrarily large point sets in general position in ℝ^d having no holes of size O(4^ddlog d) or more. This improves the previously known upper bound of order d^d+o(d) due to Valtr. The basic version of our construction uses a certain type of equidistributed point sets, originating from numerical analysis, known as (t,m,s)-nets or (t,s)-sequences, yielding a bound of 2^7d. The better bound is obtained using a variant of (t,m,s)-nets, obeying a relaxed equidistribution condition.

Related

• Fixing a hole
• Tight bounds on the expected number of holes in random point sets
• Compatible 4-Holes in Point Sets
• Large convex holes in random point sets
• Large area convex holes in random point sets