Computing a largest empty anchored cylinder, and related problems
- Publikationstyp:
- Konferenzbeitrag
- Metadaten:
-
- Autoren
- Frank Follert
- Elmar Schömer
- Jürgen Sellen
- Michiel Smid
- Christian Thiel
- DOI
- 10.1007/3-540-60692-0_65
- eISSN
- 1611-3349
- ISBN-13
- 9783540606925
- ISSN
- 0302-9743
- Online publication date
- 2005
- Paginierung
- 428 - 442
- Datum der Veröffentlichung
- 1995
- Status
- Published
- Herausgeber
- Springer Berlin Heidelberg
- Herausgeber URL
- http://dx.doi.org/10.1007/3-540-60692-0_65
- Datum der Datenerfassung
- 2020
- Titel
- Computing a largest empty anchored cylinder, and related problems
Datenquelle: Crossref
- Andere Metadatenquellen:
-
- Abstract
- Let S be a set of n points in ℝ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 minp∈S w(p) ·d(p, R) (resp. minp∈S w(p) ·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 log5n) 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.
- Autoren
- Frank Follert
- Elmar Schömer
- Jürgen Sellen
- Michiel Smid
- Christian Thiel
- DOI
- 10.1007/3-540-60692-0_65
- Editoren
- PS Thiagarajan
- ISBN-13
- 978-3-540-49263-4
- Zeitschrift
- Foundations of Software Technology and Theoretical Computer Science
- Paginierung
- 428 - 442
- Ort der Veröffentlichung
- Berlin, Heidelberg
- Datum der Veröffentlichung
- 1995
- Herausgeber
- Springer Berlin Heidelberg
- Herausgeber URL
- http://link.springer.com/10.1007/3-540-60692-0_65
- Datum der Datenerfassung
- 2023
- Titel
- Computing a largest empty anchored cylinder, and related problems
Datenquelle: Manual
- Beziehungen:
- Eigentum von