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

Fitting a two-joint orthogonal chain to a point set


Advanced Search
Opened Access Fitting a two-joint orthogonal chain to a point set

Show item statistics
Export to
Author: Díaz Báñez, José Miguel
Amaro López, M. A.
Mora, M.
Seara Ojea, Carlos
Ventura Molina, Inmaculada
Department: Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI)
Date: 2010
Published in: Computational Geometry, 44 (3), 135-147.
Document type: Article
Abstract: We study the problem of fitting a two-joint orthogonal polygonal chain to a set S of n points in the plane, where the objective function is to minimize the maximum orthogonal distance from S to the chain. We show that this problem can be solved in Θ(n) time if the orientation of the chain is fixed, and in Θ(n logn) time when the orientation is not a priori known. Moreover, our algorithm can be used to maintain the rectilinear convex hull of S while rotating the coordinate system in O(n logn) time and O(n) space, improving on a recent result (Bae et al., 2009 [4]). We also consider some variations of the problem in three-dimensions where a polygonal chain is interpreted as a configuration of orthogonal planes. In this case we obtain O(n), O(n logn), and O(n2) time algorithms depending on which plane orientations are fixed.
Cite: Díaz Báñez, J.M., Amaro López, M.A., Mora, M., Seara, C. y Ventura Molina, I. (2010). Fitting a two-joint orthogonal chain to a point set. Computational Geometry, 44 (3), 135-147.
Size: 279.1Kb
Format: PDF


DOI: 10.1016/j.comgeo.2010.07.005

See editor´s version

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

This item appears in the following Collection(s)