Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


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
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
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): 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:
Hide details for BibTeXBibTeX
  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},