de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

#### Computing a largest empty anchored cylinder, and related problems

##### MPG-Autoren
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;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

MPI-I-95-1-001.pdf
(beliebiger Volltext), 220KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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.

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