Topologically sweeping an arrangement.(English)Zbl 0676.68013
Many computation geometric problems in the plane may be solved by constructing and searching planar line arrangements, see e.g. papers byB. Chazelle,L. Guibas,D. T. Lee [BIT 25, 76-90 (1985;Zbl 0603.68072)] andH. Edelsbrunner,J. O’Rourke,R. Seidel [SIAM J. Comput. 15, 341-363 (1986;Zbl 0603.68104)] where optimal \(0(n^ 2)\) time and space algorithms are given for constructing planar line arrangements. In many cases, however, it turns out that one actually needs not to construct the whole arrangement explicitly but rather enumerate its elements in some (partial) order.
The present paper gives an algorithm to accomplish this using only 0(n) space. The method used is the generalization of the well-known sweepline paradigm called topological line sweep where the topological line may be viewed as a y-monotone curve moving from left to right not as a whole but “stretching out” in amoeba-like way. This leads to space or/and time improvements for a number of problems discussed in the paper. See also the paper ofL. Guibas,R. Seidel [Discrete Comput. Geom. 2, 175-193 (1987;Zbl 0623.68043)] for another implementation of the topological sweep for overlaying planar convex maps in time linear in the \(input+output\) size.
The present paper gives an algorithm to accomplish this using only 0(n) space. The method used is the generalization of the well-known sweepline paradigm called topological line sweep where the topological line may be viewed as a y-monotone curve moving from left to right not as a whole but “stretching out” in amoeba-like way. This leads to space or/and time improvements for a number of problems discussed in the paper. See also the paper ofL. Guibas,R. Seidel [Discrete Comput. Geom. 2, 175-193 (1987;Zbl 0623.68043)] for another implementation of the topological sweep for overlaying planar convex maps in time linear in the \(input+output\) size.
Reviewer: N.Korreanko
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68U99 | Computing methodologies and applications |
Keywords:
computational geometry;topological sweep;duality transform;amortized complexity analysis;line arrangements;sweepline paradigmCite
Full Text:DOI
References:
| [1] | Asano, T.; Asano, T.; Guibas, L. J.; Hershberger, J.; Imai, H., Visibility-polygon search and euclidean shortest paths, (Proceedings, 26th Annual Found. of Comput. Sci. Symposium (1985)), 155-164 |
| [2] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA ·Zbl 0286.68029 |
| [3] | Avis, D.; Rappaport, D., Computing the largest empty convex subset of a set of points, (Proceedings, 1st ACM Symposium on Comput. Geom. (1985)), 161-167 |
| [4] | Bentley, J.; Saxe, J. B., Decomposable searching problems 1. Static to dynamic transformation, J. Algorithms, 1, 301-358 (1980) ·Zbl 0461.68065 |
| [5] | Chazelle, B. M.; Guibas, L. J.; Lee, D. T., The power of geometric duality, BIT, 25, 76-90 (1985) ·Zbl 0603.68072 |
| [6] | Chvatàl, V.; Klincsek, G., Finding largest convex subsets, (Proceedings, 11th SE Conf. on Combin., Graph Theory and Comput (1980)) ·Zbl 0474.52004 |
| [7] | Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer-Verlag: Springer-Verlag Heidelberg ·Zbl 0634.52001 |
| [8] | Edelsbrunner, H.; Mücke, E. P., Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms (1987), manuscript |
| [9] | Edelsbrunner, H.; Guibas, L. J.; Stolfi, J., Optimal point location in a monotone subdivision, SIAM J. Comput., 15, 317-340 (1986) ·Zbl 0602.68102 |
| [10] | Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing arrangements of lines and hyperplanes with appllications, SIAM J. Comput., 15, 317-340 (1986) ·Zbl 0603.68104 |
| [11] | Edelsbrunner, H.; Overmars, M. H.; Wood, D., Graphics in flatland: A case study, (Preparata, F. P., Advances in Computing Research, 1 (1983), Jai: Jai Greenwich, CT), 35-59 |
| [12] | Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Composition Math., 2, 463-470 (1935) ·JFM 61.0651.04 |
| [13] | Erdös, P.; Szekeres, G., On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest, 3, 53-62 (1960) ·Zbl 0103.15502 |
| [14] | Edelsbrunner, H.; Welzl, E., Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput., 15, 271-284 (1986) ·Zbl 0613.68043 |
| [15] | Fabella, G.; O’Rourke, J., Twenty-two points with No Empty Hexagon, (Rep. JHU/EECS-8603 (1986), Dept. of Electri. Engin. and Comput. Sci. Johns Hopkins University: Dept. of Electri. Engin. and Comput. Sci. Johns Hopkins University Baltimore, MD) |
| [16] | Fredman, M. L., On the information theoretic lower bound, Theoret. Comput. Sci., 1, 355-361 (1976) ·Zbl 0327.68056 |
| [17] | Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, (Proceedings, 21st Annual Found. of Comput. Sci. Symposium (1984)), 338-346 |
| [18] | Grünbaum, B., Arrangements and Spreads, (Reg. Conf. Ser. Math. (1972), Amer. Math. Soc: Amer. Math. Soc Providence, RI) ·Zbl 0249.50011 |
| [19] | Guibas, L. J.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, 74-123 (1985) ·Zbl 0586.68059 |
| [20] | Harborth, H., Konvexe-Fünfecke in ebenen Punkmengen, Elem. Math., 33, 116-118 (1978) ·Zbl 0397.52005 |
| [21] | Horton, J. D., Sets with no empty convex 7-gon, Canad. Math. Bull., 26, 482-484 (1983) ·Zbl 0521.52010 |
| [22] | Knuth, D. E., (The Art of Computer Programming, Vol. I, Fundamental Algorithms (1971), Addison-Wesley: Addison-Wesley Reading, MA) |
| [23] | Lee, D. T., Proximity and Reachability in the Plane, (Ph. D. thesis (1979), Dept. Elec. Engin., University of Illinois) |
| [24] | Lee, D. T.; Preparata, F. P., Euclidean shortest paths in the presence of rectilinear barriers, Network, 14, 393-410 (1984) ·Zbl 0545.90098 |
| [25] | McKenna, M.; Seidel, R., Finding the optimal shadow of a convex polytope, (Proceedings, 1st ACM Syrup. on Comput. Geom. (1985)), 24-28 |
| [26] | Nievergelt, J.; Preparata, F. P., Plane-sweep algorithms for intersecting geometric figures, Comm. ACM, 25, 739-747 (1982) ·Zbl 0491.68075 |
| [27] | Preparata, F. P.; Shamos, M. I., Computational Geometry, an Introduction (1985), Springer-Verlag: Springer-Verlag New York/Berlin ·Zbl 0575.68059 |
| [28] | M.Sharir, personal communication, 1985.; M.Sharir, personal communication, 1985. |
| [29] | R. E.Tarjan, Amortized computational complexity,SIAM J. Comput., in press.; R. E.Tarjan, Amortized computational complexity,SIAM J. Comput., in press. ·Zbl 0599.68046 |
| [30] | Welzl, W., Constructing the visibility graph for \(n\) line segments in \(O(n^2)\) time, Inform. Process. Lett., 20, 167-171 (1985) ·Zbl 0573.68036 |
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.
