The siphon problem

Description

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.

Abstract

Ministerio de Ciencia y Tecnologia

Abstract

Fondo Europeo de Desarrollo Regional

Abstract

Generalitat de Catalunya

Additional details