# 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

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

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-95-1-001.pdf | 73 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},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-95-1-001},`

` MONTH = {January},`

` YEAR = {1995},`

` ISSN = {0946-011X},`

`}`