# Item

ITEM ACTIONSEXPORT

Released

Report

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

##### MPS-Authors

##### 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