Computing a largest empty anchored cylinder, and related problems

Let S be a set of n points in R-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 (reap. a line I through the origin) such that min(p is an element of S)w(p).d(p, R) (resp. min(p is an element of S)w(p).d(p, l)) is maximal. If all weights are one, this corresponds to computing a silo emanating from the origin (reap. 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.