Abstract
We derive algorithms for approximating a set S of n points in the plane by an x-monotone rectilinear polyline with k horizontal segments. The quality of the approximation is measured by the maximum distance from a point in S to the segment above or below it. We consider two types of problems: min-ε, where the goal is to minimize the error for k horizontal segments and min-#, where the goal is to minimize the number of segments for error ε. After O(n) preprocessing time, we solve the latter in O(min{klogn, n}) time per instance. We then solve the former in O(min{n2, nklog n}) time. We also describe an approximation algorithm for the min-ε problem that computes a solution within a factor of 3 of the optimal error for k segments, or with at most the same error as the k-optimal but using 2k–1 segments. Both approximations run in O(nlog n) time.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chan, S., Chin, F.: Approximation of polygonal curves with minimum number of line segments or minimum error. International Journal of Computational Geometry and Applications 6, 59–77 (1996)
Díaz-Bánez, J.M., Gomez, F., Hurtado, F.: Approximation of point sets by 1-corner polygonal chains. INFORMS Journal on Computing 12, 317–323 (2000)
Díaz-Bánez, J.M., Mesa, J.A.: Fitting rectilinear polygonal curves to a set of points in the plane. European Journal of Operations Research 130, 214–222 (2001)
Eu, D., Toussaint, G.T.: On approximating polygonal curves in two and three dimensions. CVGIP: Graphical Models and Image Processing 56(3), 231–246 (1994)
Hakimi, S.L., Schmeichel, E.F.: Fitting polygonal functions to a set of points in the plane. CVGIP: Graphical Models and Image Processing 53(2), 132–136 (1991)
Imai, H., Iri, M.: Computational-geometric methods for polygonal approximations of a curve. Computer Vision, Graphics and Image Processing 36(1), 31–41 (1986)
Imai, H., Iri, M.: An optimal algorithm for approximating a piecewise linear function. Journal of Information Processing 9(3), 159–162 (1986)
Imai, H., Iri, M.: Polygonal approximations of a curve – formulations and algorithms. In: Toussaint, G.T. (ed.) Computational Morphology, pp. 71–86. North-Holland, Amsterdam (1988)
Melkman, A., O’Rourke, J.: On polygonal chain approximation. In: Toussaint, G.T. (ed.) Computational Morphology, pp. 87–95. North-Holland, Amsterdam (1988)
Varadarajan, K.R.: Approximating Monotone Polygonal Curves Using the Uniform Metric. In: SCG 1994 Proceedings of the 12th annual symposium on Computational geometry, pp. 311–318 (1996)
Wang, D.P.: A new algorithms for fitting a rectilinear x-monotone curve to a set of points in the plane. Pattern Recognition Letters 23, 329–334 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mayster, Y., Lopez, M.A. (2006). Rectilinear Approximation of a Set of Points in the Plane. In: Correa, J.R., Hevia, A., Kiwi, M. (eds) LATIN 2006: Theoretical Informatics. LATIN 2006. Lecture Notes in Computer Science, vol 3887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11682462_65
Download citation
DOI: https://doi.org/10.1007/11682462_65
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32755-4
Online ISBN: 978-3-540-32756-1
eBook Packages: Computer ScienceComputer Science (R0)