Artículo
Fitting a two-joint orthogonal chain to a point set
Autor/es | Díaz Báñez, José Miguel
Amaro López, M. A. Mora, M. Seara Ojea, Carlos Ventura Molina, Inmaculada |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) |
Fecha de publicación | 2010 |
Fecha de depósito | 2018-08-09 |
Publicado en |
|
Resumen | 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 ... 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. |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
1-s2.0-S092577211000060X-main.pdf | 279.1Kb | [PDF] | Ver/ | |