de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Computing a largest empty anchored cylinder, and related problems

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45612

Thiel,  Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45414

Schömer,  Elmar
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-95-1-001.pdf
(Any fulltext), 220KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Smid, M., Thiel, C., Follert, F., Schömer, E., & Sellen, J.(1995). Computing a largest empty anchored cylinder, and related problems (MPI-I-1995-1-001). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A83F-8
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