Ponencia
The siphon problem
Autor/es | Díaz Báñez, José Miguel
Seara Ojea, Carlos Ventura Molina, Inmaculada |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSII) |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-01 |
Publicado en |
|
Resumen | 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. |
Identificador del proyecto | MCYT BFM2000-1052-C02-01
MCYT-FEDER TIC-2001-2171 BFM 2002-0557 2001SGR00224 |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
The siphon problem.pdf | 128.5Kb | [PDF] | Ver/ | |