Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Fitting a two-joint orthogonal chain to a point set

Autor
Díaz, J.; López, M.; Mora, M.; Seara, C.; Ventura, I.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2011-04
Volum
44
Número
3
Pàgina inicial
135
Pàgina final
147
DOI
https://doi.org/10.1016/j.comgeo.2010.07.005 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/12026 Obrir en finestra nova
Resum
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 log n) time when the orientation is not a priori known. We also consider some variations of the problem in three-dimensions where a polygonal chain is interpreted as a configuration of or...
Citació
Díaz-Báñez, J.M. [et al.]. Fitting a two-joint orthogonal chain to a point set. "Computational geometry. Theory and applications", Abril 2011, vol. 44, núm. 3, p. 135-147.
Grup de recerca
CGA -Computational Geometry and Applications
DCG - Discrete and Combinatorial Geometry

Participants

Arxius