MPI-I-95-1-001
Computing a largest empty anchored cylinder, and related problems
Smid, Michiel and Thiel, Christian and Follert, F. and Schömer, Elmar and Sellen, J.
January 1995, 17 pages.
.
Status: available - back from printing
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
-
MPI-I-95-1-001.pdf
- Attachement: MPI-I-95-1-001.ps.gz (73 KBytes); MPI-I-95-1-001.pdf (219 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-001
BibTeX
@TECHREPORT{SmidThielFollertSchoemerSellen95,
AUTHOR = {Smid, Michiel and Thiel, Christian and Follert, F. and Sch{\"o}mer, Elmar and Sellen, J.},
TITLE = {Computing a largest empty anchored cylinder, and related problems},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-95-1-001},
MONTH = {January},
YEAR = {1995},
ISSN = {0946-011X},
}