# zbMATH — the first resource for mathematics

On determining the on-line minimax linear fit to a discrete point set in the plane. (English) Zbl 0637.68075
Summary: An on-line algorithm for obtaining the minimax linear fit to a planar discrete set of points is presented. The algorithm depends on a new property of the convex hull. This property deals with the maximum vertical distance between a hull edge and the vertices of the hull. It states that, for consecutive bottom hull edges, this maximum vertical distance monotonically decreases to a minimum and then monotonically increases. An analogous property applies for the top hull.
##### MSC:
 68R99 Discrete mathematics in relation to computer science 68Q25 Analysis of algorithms and problem complexity 52A10 Convex sets in $$2$$ dimensions (including convex curves) 68W99 Algorithms in computer science
Full Text:
##### References:
 [1] Andrew, A.M., Another efficient algorithm for convex hulls in two dimensions, Inform. process. lett., 9, 5, 216-219, (1979) · Zbl 0423.68032 [2] Avis, D.; El Gindy, H.; Seidel, R., Simple on-line algorithms for convex polygons, () [3] Avis, D.; Toussaint, G.T.; Bhattacharya, B.K., On the multimodality of distances in convex polygons, Comput. math. & appl., 8, 2, 153-156, (1982) · Zbl 0487.68062 [4] Barrodale, I.; Phillips, C., Solution to an overdetermined system of linear equations in the Chebyshev norm, ACM trans. math. software, 1, 3, 264-270, (1975) · Zbl 0309.65015 [5] Barrodale, I.; Phillips, C., An improved algorithm for discrete Chebyshev linear approximation, (), 177-190 · Zbl 0358.65060 [6] Bentley, J.L.; Shamos, M.I., Divide and conquer in linear expected time, Inform. process. lett., 7, 2, 87-91, (1978) · Zbl 0404.68046 [7] Bykat, A., Convex hull of a finite set of points in two dimensions, Inform. process. lett., 7, 6, 296-298, (1978) · Zbl 0392.52002 [8] Cheney, E.W., Introduction to approximation theory, (1966), McGraw-Hill New York · Zbl 0161.25202 [9] Eddy, W.F.; Eddy, W.F., A new convex hull algorithm for planar sets, ACM trans. math. software, ACM trans. math. software, 3, 411-412, (1977) · Zbl 0355.60031 [10] Graham, R.L., An efficient algorithm for determining the convex hull of a finite planar set, Inform. process. lett., 1, 4, 132-133, (1972) · Zbl 0236.68013 [11] Jarvis, R.A., On the identification of the convex hull of a finite set of points in the plane, Inform. process. lett., 2, 1, 18-21, (1973) · Zbl 0256.68041 [12] Knuth, D.E., () [13] Madsen, K.; Powell, M.J.D., Fortran subroutine that calculates the minimax solution of linear equations subject to bounds on the variables, (1975), Computer Science and Systems Division, AERE Harwell Oxfordshire, U.K, Rept. [14] Overmars, M.H.; van Leeuwen, J., Maintenance of configurations in the plane, J. comput. system sci., 23, 2, 166-204, (1981) · Zbl 0474.68082 [15] Powell, M.J.D., The exchange algorithm on a discrete point set, () · Zbl 0462.90062 [16] Powell, M.J.D.; Powell, M.J.D., Minimax solution of linear equations subject to bounds on the variables, (), (1974), Computer Science and Systems Division, Atomic Energy Research Establishment Harwell, Oxfordshire, U.K, Rept. · Zbl 0324.65030 [17] Preparata, F.P., An optimal real time algorithm for planar convex hulls, Comm. ACM, 22, 7, 402-405, (1979) · Zbl 0404.68069 [18] Preparata, F.P.; Hong, S.J., Convex hulls of finite sets in two or three dimensions, Comm. ACM, 20, 2, 87-93, (1977) · Zbl 0342.68030 [19] Shamos, M.I., Geometric complexity, (), 224-233 [20] Shamos, M.I., Computational geometry, (), 68-72 [21] Toussaint, G.T., Solving geometric problems with the “rotating calipers”, (), A10.02-A10.05 [22] Toussaint, G.T., Complexity, convexity, and unimodality, Internat. J. comput. engrg. sci., 13, 3, 197-217, (1984) · Zbl 0555.68061 [23] Toussaint, G.T., On the complexity of approximating polygonal curves in the plane, () · Zbl 0528.65005
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.