Abstract
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum criteria with respect to L 1- and L 2-metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We present efficient algorithms for the 1-joint versions of the problem, and fully polynomial-time approximation schemes for the general k-joint versions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aggarwal, A., Schieber, B., Tokuyama, T.: Finding a minimum-weight k-link path in graphs with the concave Monge property and applications. Discrete Comput. Geom. 12, 263–280 (1994)
Agarwal, P., Aronov, B., Chan, T., Sharir, M.: On Levels in Arrangements of Lines, Segments, Planes, and Triangles. Discrete Comput. Geom. 19, 315–331 (1998)
Agarwal, P., Matoušek, J.: Ray shooting and parametric search. SIAM J. Comput. 22, 794–806 (1993)
Chun, J., Sadakane, K., Tokuyama, T.: Linear time algorithm for approximating a curve by a single-peaked curve. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 6–16. Springer, Heidelberg (2003)
Clarkson, K.L., Shor, P.W.: Application of Random Sampling in Computational Geometry. Discrete Comput. Geom. 4, 423–432 (1989)
Goodrich, M.: Efficient piecewise-linear function approximation using the uniform metric. Discrete Comput. Geom. 14, 445–462 (1995)
Hakimi, S., Schmeichel, E.: Fitting polygonal functions to a set of points in the plane. Graphical Models and Image Processing 53, 132–136 (1991)
Imai, H., Kato, K., Yamamoto, P.: A linear-time algorithm for linear L 1 approximation of points. Algorithmica 4, 77–96 (1989)
Katoh, N., Tokuyama, T.: Notes on computing peaks in k-levels and parametric spanning trees. In: Proc. 17th ACM Symp. on Computational Geometry, pp. 241–248 (2001)
Langerman, S., Steiger, W.: Optimization in arrangements. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 50–61. Springer, Heidelberg (2003)
Matoušek, J.: Efficient partition trees. Discrete Comput. Geom. 8, 315–334 (1992)
Matoušek, J.: Range searching with efficient hierarchical cutting. In: Proc. 8th ACM Symp. on Comput. Geom, pp. 276–287 (1992)
Matoušek, J.: Geometric range searching. ACM Computing Surveys 26, 421–461 (1994)
Matoušek, J., Schwarzkopf, O.: Linear optimization queries. In: Proc. 8th Annual ACM Symp. Comput. Geom, pp. 16–25 (1992)
Preparata, F.P., Shamos, M.I.: Computational Geometry, an Introduction. Springer-Verlag, New York (1985)
Salowe, J.: Parametric Search. In: Goodman, J., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, vol. 37, CRC Press, Boca Raton (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aronov, B., Asano, T., Katoh, N., Mehlhorn, K., Tokuyama, T. (2004). Polyline Fitting of Planar Points Under Min-sum Criteria. In: Fleischer, R., Trippen, G. (eds) Algorithms and Computation. ISAAC 2004. Lecture Notes in Computer Science, vol 3341. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30551-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-30551-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24131-7
Online ISBN: 978-3-540-30551-4
eBook Packages: Computer ScienceComputer Science (R0)