Opened Access The siphon problem
Cites
Show item statistics
Icon
Export to
Author: Díaz Báñez, José Miguel
Seara Ojea, Carlos
Ventura Molina, Inmaculada
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2004
Document type: Presentation
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 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.
Size: 128.5Kb
Format: PDF

URI: http://hdl.handle.net/11441/55024

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)