Abstract
Let S={s 1, s 2,...,s n } be a set of sites in E d, where every site s i has a positive real weight ω i . This paper gives an algorithm to find a weighted orthogonal L ∞-approximation hyperplane for S. The algorithm is shown to require O(nlogn) time and O(n) space for d=2, and O(n [d/2+1]) time and O(n [(d+1)/2]) space for d>2. The L ∞-approximation algorithm will be adapted to solve the problem of finding the width of a set of n points in E d, and the problem of finding a stabbing hyperplane for a set of n hyperspheres in E d with varying radii. The time and space complexities of the width and stabbing algorithms are seen to be the same as those of the L ∞-approximation algorithm.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Atallah, M. and Bajaj, C. Efficient Algorithms for Common Transversals, Inf. Proc. Letters 25 (1987), pp. 87–91.
Avis, D. and Doskas, M. Algorithms for High Dimensional Stabbing Problems, Tech. Rept. SOCS-87.2, McGill Univ., January 1987.
Avis, D., Robert, J.-M., and Wenger, R. Lower Bounds for Line Stabbing, in preparation.
Bajaj, C. and Li, M. On the Duality of Intersection and Closest Points, in “Proc. 21st Ann. Allerton Conf. 1983”, pp. 459–460.
Borsuk, K. Multidimensional Analytic Geometry, Polish Scientific Publishers, Warsaw, 1969.
Brown, K. Q. Geometric Transforms for Fast Geometric Algorithms, Ph.D. Thesis, Rep. CMU-CS-80-101, Dept. Comp. Sci., Carnegie-Mellon Univ., Pittsburgh, PA, 1980.
Chvátal, V. Linear Programming, W. H. Freeman and Co., New York, 1983.
Edelsbrunner, H. Finding Transversals for Sets of Simple Geometric Figures, Theo. Comp. Sc. 35 (1985), pp. 55–69.
Edelsbrunner, H., Guibas, L. J., and Sharir, M. The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications, Tech. Rept. UIUCDCS-R-87-1390, Univ. of Illinois at Urbana-Champaign, November 1987.
Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D. Stabbing Line Segments, BIT 22 (1982), pp. 274–281.
Hershberger, J. private communication.
Houle, M. E. and Robert, J.-M. Orthogonal Weighted Linear Approximation and Applications, Tech. Rept. SOCS-88.13, McGill Univ., August 1988.
Houle, M. E. and Toussaint, G. T. Computing the Width of a Set, IEEE Trans. Pattern Anal. Machine Intell. 10 (1988), pp. 761–765.
Imai, H., Imai, K., and Yamamoto, P. Algorithms for Orthogonal L 1 Linear Approximation of Points in Two and Higher Dimensions, “13th Int. Symp. on Math. Prog. 1988”, Tokyo.
Kurozumi, Y. and Davis, W. A. Polygonal Approximation by the Minimax Method, Computer Graphics and Image Processing, 19 (1982), pp. 248–264.
Lee, D. T. and Wu, Y. F. Geometric Complexity of Some Location Problems, Algorithmica 1 (1986), pp. 193–212.
Morris, J. G. and Norback, J. P. Linear Facility Location — Solving Extensions of the Basic Problem, Eur. J. Oper. Res. 12 (1983), pp. 90–94.
Preparata, F. P. and Hong, S. J. Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Comm. ACM 20 (1977), pp. 87–93.
Seidel, R. A Convex Hull Algorithm Optimal for Points in Even Dimensions, Tech. Rept. 81-14, Univ. British Columbia, 1981.
Yamamoto, P., Kato, K., Imai, K. and Imai, H. Algorithms for Vertical and Orthogonal L 1 Linear Approximation of Points, in “Proc. 4th Ann. ACM Symp. Comp. Geom., 1988”, pp. 352–361.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Houle, M.E., Imai, H., Imai, K., Robert, JM. (1989). Weighted orthogonal linear L ∞-approximation and applications. In: Dehne, F., Sack, J.R., Santoro, N. (eds) Algorithms and Data Structures. WADS 1989. Lecture Notes in Computer Science, vol 382. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51542-9_16
Download citation
DOI: https://doi.org/10.1007/3-540-51542-9_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51542-5
Online ISBN: 978-3-540-48237-6
eBook Packages: Springer Book Archive