max planck institut
informatik

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.

MPI-I-95-1-001. January 1995, 17 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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
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
In the final part of the paper, we consider some related problems
Acknowledgement:
References to related material:

MPI-I-95-1-001.pdf73 KBytes; 219 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://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},