Computing a Largest Empty Anchored Cylinder, and Related Problems
Frank Follert, Elmar Schömer, Jürgen Sellen, Michiel Smid, Christian Thiel · International Journal of Computational Geometry & Applications · 1997
Let S be a set of n points in ℝd, and let each point p of S have a positive weight w(p). We consider the problem of computing a ray R emanating from the origin (resp. a line l through the origin) such that min p ∈ s w(p) · d(p,R) ( resp. min p ∈ S w(p) · d(p,l)) is maximal. If all weights are one, this corresponds to computing a silo emanating from the origin ( resp. a cylinder whose axis contains the origin) that does not contain any point of S and whose radius is maximal. For d = 2, we show how to solve these problems in O(n log n) time, which is optimal in the algebraic computation tree model. For d = 3, we give algorithms that are based on the parametric search technique and run in O(n log 4 n) time. The previous best known algorithms for these three-dimensional problems had almost quadratic running time. In the final part of the paper, we consider some related problems.