On Visibility Problems with an Infinite Discrete, set of Obstacles

2018/05/29 by Boshernitzan, Michael, Solomon, Yaar
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1805.11679

Abstract

This paper studies visibility problems in Euclidean spaces ℝ^d where the obstacles are the points of infinite discrete sets Y⊆ℝ^d. A point x∈ℝ^d is called ε-visible for Y (notation: x\invis(Y, ε)) if there exists a ray L⊆ℝ^d emanating from x such that ||y-z||≥ε, for all y∈ Y∖\x\ and z∈ L. A point x∈ℝ^d is called visible for Y (notation: x\invis(Y)) if x\invis(Y, ε)), for some ε>0. Our main result is the following. For every ε>0 and every relatively dense set Y⊆ℝ², vis(Y, ε))≠ℝ². This result generalizes a theorem of Dumitrescu and Jiang, which settled Mitchell's dark forest conjecture. On the other hand, we show that there exists a relatively dense subset Y⊆ ℤ^d such that vis(Y)=ℝ^d. (One easily verifies that vis(ℤ^d)=ℝ^d∖ℤ^d, for all d≥ 2). We derive a number of other results clarifying how the size of a sets Y⊆ℝ^d may affect the sets vis(Y) and vis(Y,ε). We present a Ramsey type result concerning uniformly separated subsets of ℝ² whose growth is faster than linear.

Related

• Danzer's Problem, Effective Constructions of Dense Forests and Digital Sequences
• Dense Forests Constructed from Grids
• On Visibility Graphs of Point Sets in the Plane
• Unsolved Problems in Visibility Graphs of Points, Segments and Polygons
• A New Upper Bound for the VC-Dimension of Visibility Regions