Presentation
The siphon problem
Author/s | Díaz Báñez, José Miguel
Seara Ojea, Carlos Ventura Molina, Inmaculada |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSII) |
Publication Date | 2004 |
Deposit Date | 2017-03-01 |
Published in |
|
Abstract | An α-siphon is the locus of points in the plane that are at the same distance ǫ from a polygonal chain consisting of two half-lines emanating from a common point such that α is the interior angle of the half-lines. Given ... An α-siphon is the locus of points in the plane that are at the same distance ǫ from a polygonal chain consisting of two half-lines emanating from a common point such that α is the interior angle of the half-lines. Given a set S of n points in the plane and a fixed angle α, we want to compute an α-siphon of largest width ǫ such that no points of S lies in its interior. We present an efficient O(n2)-time algorithm for computing an orthogonal siphon. The approach can be handled to solve the problem of the oriented α-siphon for which the orientation of a half-line is known. We also propose an O(n3 log n)-time algorithm for the arbitrarily oriented version. |
Project ID. | MCYT BFM2000-1052-C02-01
MCYT-FEDER TIC-2001-2171 BFM 2002-0557 2001SGR00224 |
Citation | Díaz Báñez, J.M., Seara Ojea, C. y Ventura Molina, I. (2004). The siphon problem. En 20th European Workshop on Computational Geometry, Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
The siphon problem.pdf | 128.5Kb | [PDF] | View/ | |