Fitting a two-joint orthogonal chain to a point set. (English) Zbl 1209.65019
Summary: 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 \(\varTheta (n)\) time if the orientation of the chain is fixed, and in \(\varTheta (n \log n)\) 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 \log n)\) time and \(O(n)\) space, improving on a recent result [S. W. Bae et al., Comput. Geom. 42, No. 9, 903–912 (2009; Zbl 1175.49035)]. 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 \log n)\), and \(O(n^{2})\) time algorithms depending on which plane orientations are fixed.
MSC:
| 65D10 | Numerical smoothing, curve fitting |
Citations:
Zbl 1175.49035References:
| [1] | Aronov, B.; Asano, T.; Katoh, N.; Melhorn, K.; Tokuyama, T., Polyline fitting of planar points under min-sum criteria, International Journal of Computational Geometry and Applications, 16, 2-3, 97-116 (2006) · Zbl 1098.65011 |
| [2] | Avis, D.; Beresford-Smith, B.; Devroye, L.; Elgindy, H.; Guvremont, E.; Hurtado, F.; Zhu, B., Unoriented \(Θ\)-maxima in the plane: complexity and algorithms, SIAM Journal of Computing, 28, 1, 278-296 (1999) · Zbl 0914.68102 |
| [3] | Avis, D.; Elgindy, H.; Seidel, R., Simple on-line algorithms for convex polygons, (Toussaint, G. T., Computational Geometry (1985), North-Holland: North-Holland Amsterdam), 23-42 · Zbl 0588.68057 |
| [4] | Bae, S. W.; Lee, C.; Ahn, H.-K.; Choi, S.; Chwa, K.-Y., Computing minimum-area rectilinear convex hull and \(L\)-shape, Computational Geometry: Theory and Applications, 42, 903-912 (2009) · Zbl 1175.49035 |
| [5] | Burt, P. J., Fast filter transforms for image processing, Computer Graphics and Image Processing, 16, 20-51 (1979) |
| [6] | Chan, W. S.; Chin, F., Approximation of polygonal curves with minimum number of line segments or minimun error, International Journal of Computational Geometry and Applications, 6, 59-77 (1996) · Zbl 0851.68110 |
| [7] | D.Z. Chen, H. Wang, Approximating points by piecewise linear functions: I, in: Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, pp. 224-233.; D.Z. Chen, H. Wang, Approximating points by piecewise linear functions: I, in: Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, pp. 224-233. · Zbl 1272.52008 |
| [8] | D.Z. Chen, H. Wang, Approximating points by piecewise linear functions: II, in: Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, pp. 234-243.; D.Z. Chen, H. Wang, Approximating points by piecewise linear functions: II, in: Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, pp. 234-243. · Zbl 1272.52009 |
| [9] | Chin, F.; Choi, A.; Luo, Y., Optimal generating kernel for image pyramids by piecewise fitting, IEEE Transactions on Pattern Analysis and Machine Intelligence, 14, 1190-1198 (1992) |
| [10] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press · Zbl 1047.68161 |
| [11] | Díaz-Báñez, J. M.; Mesa, J. A., Fitting rectilinear polygonal curves to a set of points in the plane, European Journal of Operations Research, 130, 1, 214-222 (2001) · Zbl 1068.65034 |
| [12] | Edelsbrunner, H., Computing the extreme distances between two convex polygons, Journal of Algorithms, 6, 213-224 (1985) · Zbl 0604.68079 |
| [13] | Fournier, H.; Vigneron, A., Fitting a Step Function to a Point Set, Lecture Notes in Computer Science, vol. 5193 (2008), pp. 442-453 · Zbl 1158.68551 |
| [14] | Goodrich, M. T., Efficient piecewise-linear function approximation using the uniform metric, Discrete and Computational Geometry, 14, 445-462 (1995) · Zbl 0841.68121 |
| [15] | Guha, S.; Shim, K., A note on linear time algorithms for maximum error histograms, IEEE Transactions on Knowledge and Data Enginering, 19, 7, 993-997 (2007) |
| [16] | Guibas, L. J.; Hershberger, J. E.; Mitchell, J. S.B.; Snoeyink, J. S., Approximating polygons and subdivisions with minimum-link paths, International Journal of Computational Geometry and Applications, 3, 383-415 (1993) · Zbl 0803.68134 |
| [17] | Hakimi, S. L.; Schmeichel, E. F., Fitting polygonal functions to a set of points in the plane, Graphical Models and Image Processing, 53, 132-136 (1991) · Zbl 0808.68107 |
| [18] | Hershberger, J.; Suri, S., Applications of a semi-dynamic convex hull algorithm, BIT, 32, 2, 249-267 (1992) · Zbl 0761.68097 |
| [19] | Houle, M. E.; Toussaint, G. T., Computing the width of a set, IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 5, 761-765 (1988) · Zbl 0659.68067 |
| [20] | Imai, H.; Iri, M., Polygonal approximations of a curve—Formulations and algorithms, (Computational Morphology (1988), Elsevier Science Publisher B.V./North-Holland), 71-86 · Zbl 0657.65025 |
| [21] | Kung, H. T.; Luccio, F.; Preparata, F. P., On finding the maxima of a set of vectors, Journal of ACM, 22, 469-476 (1975) · Zbl 0316.68030 |
| [22] | Preparata, F. P., An optimal real-time algorithm for planar convex hulls, Comm. ACM, 22, 7, 402-405 (1979) · Zbl 0404.68069 |
| [23] | Lee, D. T.; Wu, Y. F., Geometric complexity of some location problems, Algorithmica, 1, 193-211 (1986) · Zbl 0639.68038 |
| [24] | López, M. A.; Mayster, Y., Approximating a set of points by a step function, Journal of Visual Communication and Image Representation, 17, 6, 1178-1189 (2006) |
| [25] | Pavlidis, T., Algorithms for shape analysis of contours and waveforms, IEEE Transation on Pattern Analysis and Machine Intelligence, 301-312 (1980) |
| [26] | Preparata, F. P.; Shamos, M. I., Computational Geometry, An Introduction (1988), Springer |
| [27] | G.T. Toussaint, On the complexity of approximating polygonal curves in the plane, in: International Symposium on Robotics and Automation, Lugano, Switzerland, 1985.; G.T. Toussaint, On the complexity of approximating polygonal curves in the plane, in: International Symposium on Robotics and Automation, Lugano, Switzerland, 1985. |
| [28] | Wang, D. P., A new algorithm for fitting a rectilinear \(x\)-monotone curve to a set of points in the plane, Pattern Recognition Letters, 23, 1, 329-334 (2002) · Zbl 1050.68156 |
| [29] | Wang, D. P.; Huang, N. F.; Chao, H. S.; Lee, R. C.T., Plane Sweep Algorithms for Polygonal Approximation Problems with Applications, Lecture Notes in Computer Science, vol. 762 (1993), pp. 515-522 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
