hide
Free keywords:
-
Abstract:
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
(resp.\ a line $l$ through the origin) such that
$\min_{p\in S} w(p) \cdot d(p,R)$ (resp.
$\min_{p\in S} w(p) \cdot 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^5 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
