Abstract
The intersection radius of a set ofn geometrical objects in ad-dimensional Euclidean space,E d, is the radius of the smallest closed hypersphere that intersects all the objects of the set. In this paper, we describe optimal algorithms for some intersection radius problems. We first present a linear-time algorithm to determine the smallest closed hypersphere that intersects a set of hyperplanes inE d, assumingd to be a fixed parameter. This is done by reducing the problem to a linear programming problem in a (d+1)-dimensional space, involving 2n linear constraints. We also show how the prune-and-search technique, coupled with the strategy of replacing a ray by a point or a line can be used to solve, in linear time, the intersection radius problem for a set ofn line segments in the plane. Currently, no algorithms are known that solve these intersection radius problems within the same time bounds.
Zusammenfassung
Wir bezeichnen als Radius des Durchschnitts einer Menge vonn geometrischen Objekten imd-dimensionalen Euklidischen RaumE d Radius der kleinsten abgeschlossenen Hyperkugel, welche einen nichtleeren Durchschnitt mit allen Objekten besitzt. In der vorliegenden Arbeit beschreiben wir optimale Algorithmen zuer Bestimmung einiger solcher Radien. Zuerst stellen wir einen Algorithmus mit linearem Zeitbedarf vor, wenn die Objekte Hyperebenen inE d mit festemd sind. Er beruht auf der Reduktion des Problems auf eine (d+1)-dimensionale Lineare Optimierungsaufgabe mit 2n linearen Nebenbedingungen. Wir beschreiben auch die Lösung des Durchschnitts-Radius Problems fürn Strecken in der Ebene. Dazu benutzen wir neben Breitensuche die Ersetzung von Halbstrahlen durch Punkte oder Gerade. Bisher waren keine Algorithmen bekannt, welche diese Probleme in den gleichen Zeitschranken lösen.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bhattacharya, B. K., Czyzowicz, J., Egyed, P., Toussaint, G., Stojmenovic, I., Urrutia, J.: Computing shortest transversals of set. In: Proc. of the Seventh Annual ACM Symp. on Computational Geometry, pp. 71–80, 1991.
Brown K. Q.: Fast intersection of half spaces. Technical Report CMU-CS-78-129, Carnegie Mellon University, Pittsburg, 1978.
Bhattacharya, B. K., Toussaint, G. T.: Computing shortest transversals. Technical Report SOCS 90.6, McGill University, April 1990.
Chrystal, G.: On the problem to construct the minimum circle enclosingn given points in the plane. In: Proc. Edinberg Math. Soc.,3, 30–33 (1885).
Clarkson, K. L.: Linear programming inO(3(k+1) 2) time. Informa. Proc. Lett.22, 21–24 (1986).
Dyer, M. E.: Linear-time algorithm for two- and three-variable linear programs. SIAM J. Computing13, 31–45 (1984).
Dyer, M. E.: On a multidimensional search technique and its application to the Euclidean 1-center problem. SIAM J. Computing15, 725–738 (1986).
Goodrich, M. T., Snoeyink, J. S.: Stabbing parallel segments with a convex polygon. In: Dehne, F., Sack, J. R., Santaroo, N. (eds) Proc. of the Workshop on Algorithms and Data Structures, pp. 231–242. Berlin Heidelberg New York Tokyo: Springer 1989 (Lecture Notes in Computer Science vol. 382).
Hadwiger, H., Debrunner, H., Klee, V.: Combinatorial geometry in the plane. Toronto: Holt, Rinehart and Winston, 1964.
Houle, M. E., Imai, H., Imai, K., Robert, J. M.: Weighted orthogonal linearL ∞-approximation and applications. In: Dehne, F., Sack, J. R., Santaroo, N. (eds) Proc. of the Workshop on Algorithms and Data Structures, pp. 183–191. Berlin Heidelberg New York Tokyo: Springer 1989 (Lecture Notes in Computer Science, vol. 382).
Megiddo, N.: Linear-time algorithms for linar programming inR 3 and related problems. SIAM J. Computing12, 759–776 (1983).
Megiddo, N.: Linear programming in linear time when the dimension is fixed. JACM31, 114–127 (1984).
Meijer, H., Rappaport, D.: Minimum polygon covers of parallel line segments. Technical Report CISC 90-279, Queen's University, Canada, 1990.
Seidel, R.: Linear programming and convex hull made easy. In: Proc. of the Sixth Annual ACM Symp. on Computational Geometry, pp. 211–215, 1990.
Shamos, M. I.: Computational Geometry. PhD thesis, Department of Computer Science, 1978.
Sylvester, J. J.: A question in the geometry situation. Q. J. Pure Appl. Math.1, 79 (1857).
Sylvester, J. J.: On Poncelet's approximate linear valuation of the surd forms. Phil. Mag.20, 203–222 (1860).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bhattacharya, B.K., Jadhav, S., Mukhopadhyay, A. et al. Optimal algorithms for some intersection radius problems. Computing 52, 269–279 (1994). https://doi.org/10.1007/BF02246508
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02246508