Repositorio de producción científica de la Universidad de Sevilla

Finding a widest empty 1-corner corridor

 

Advanced Search
 
Opened Access Finding a widest empty 1-corner corridor
Cites
Show item statistics
Icon
Export to
Author: Díaz Báñez, José Miguel
López, Mario A.
Sellarès Chiva, Joan Antoni
Department: Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI)
Date: 2004
Document type: Presentation
Abstract: Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We star giving a characterization of the 1-corner corridors that we call locally widest. Our approach to finding a widest empty 1-corner corridor consists of identifying a set of 1-corner corridors locally widest, that is guaranteed to contain a solution. We describe an algorithm that solves the problem in O(n4 log n) time and O(n) space.
Cite: Díaz Báñez, J.M., López, M.A. y Sellarès Chiva, J.A. (2004). Finding a widest empty 1-corner corridor. En 20th European Workshop on Computational Geometry, Sevilla.
Size: 123.9Kb
Format: PDF

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

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

This item appears in the following Collection(s)