Abstract
An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3.
We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The design and analysis of computer algorithms. Addison Wesley, 1974.
G. L. Alexanderson and J. E. Wetzel, Simple partitions of space.Math. Mag. 51 (1978), 220–225.
F. Aurenhammer, Power diagrams: properties, algorithms, and applications. Rep. F 120, Inst. Inform. Process., Techn. Univ. Graz, Austria, 1983.
B. M. Chazelle and F. P. Preparata, Halfspatial range search: an algorithmic application ofk-sets. To appear inJ. Discrete Comput. Geom.
R. Cole, M. Sharir and C. K. Yap, Onk-hulls and related problems.Proc. 16th Ann. ACM Symp. Theor. Comput. Sci. (1984), 154–166.
D. P. Dobkin and H. Edelsbrunner, Space searching for intersecting objects.Proc. 25th Ann. IEEE Symp. Found. Comput. Sci. (1984), 387–392.
H. Edelsbrunner and F. Huber, Dissecting sets of points in two and three dimensions. Rep. F 138, Inst. Inform. Process., Techn. Univ. Graz, Austria, 1984.
H. Edelsbrunner and H. A. Maurer, Finding extreme points in three dimensions and solving the post-office problem in the plane.Inform. Process. Lett. 21 (1985), 39–47.
H. Edelsbrunner, J. O'Rourke and R. Seidel, Constructing arrangements of lines and hyperplanes with applications.Proc. 24th Ann. IEEE Symp. Found. Comput. Sci. (1983), 83–91.
H. Edelsbrunner and R. Seidel, Voronoi diagrams and arrangements.Proc. Sympos. Comput. Geom., Baltimore (1985), 251–262.
H. Edelsbrunner and G. Stoeckl, The number of extreme pairs of finite point-sets in Euclidean spaces. Rep. F 142, Inst. Inform. Process., Techn. Univ. Graz, Austria, 1984.
H. Edelsbrunner and E. Welzl, On the number of line separations of a finite set in the plane.J. Combin. Theory Ser. A 38 (1985), 15–29.
P. Erdoes, L. Lovasz, A. Simmons and E. G. Straus, Dissection graphs of planar point-sets. In:A survey of combinatorial theory, J. N. Srivastava et al. (eds.), North Holland, 1973, 139–149.
I. G. Gowda and D. G. Kirkpatrick, Exploiting linear merging and extra storage in the maintenance of fully dynamic geometric data structures.Proc. 18th Ann. Allerton Conf. Commun., Contr., Comput. (1980), 1–10.
B. Gruenbaum, Arrangements and hyperplanes.Congr. Number. III,Louis. Conf. Combin.,Graph Th., Comput. (1971), 41–106.
H. Imai, M. Iri and K. Murota, Voronoi diagram in the Laguerre metric and its applications.SIAM J. Comput. 14 (1985), 93–105.
D. E. Knuth,Searching and sorting. The art of computer programming III. Addison-Wesley, 1973.
D. T. Lee, Onk-nearest neighbour Voronoi diagram in the plane.IEEE Trans. Comput. C-31 (1982), 478–487.
H. A. Maurer and Th. Ottmann, Dynamic solutions of decomposable searching problems. In:Discrete structures and algorithms, U. Pape, (ed.), Carl Hanser (1979), 17–24.
N. Megiddo, Partitioning with two lines in the plane. To appear inJ. Algorithms.
F. P. Preparata and S. J. Hong, Convex hulls of finite sets of points in two and three dimensions.Comm. ACM (1977), 87–93.
M. I. Shamos and D. Hoey, Closest-point problems.Proc. 16th Ann. IEEE Symp. Found. Comput. Sci. (1975), 151–162.
J. van Leeuwen and D. Wood, Dynamization of decomposable searching problems.Inform. Process. Lett. 10 (1980), 51–56.
F. F. Yao, D. P. Dobkin and H. Edelsbrunner, Manuscript, 1985.
Author information
Authors and Affiliations
Additional information
Communicated by B. Chazelle.
Rights and permissions
About this article
Cite this article
Edelsbrunner, H. Edge-skeletons in arrangements with applications. Algorithmica 1, 93–109 (1986). https://doi.org/10.1007/BF01840438
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01840438