Abstract
This paper gives efficient, randomized algorithms for the following problems: (1) construction of levels of order 1 tok in an arrangement of hyperplanes in any dimension and (2) construction of higher-order Voronoi diagrams of order 1 tok in any dimension. A new combinatorial tool in the form of a mathematical series, called a θ series, is associated with an arrangement of hyperplanes inR d. It is used to study the combinatorial as well as algorithmic complexity of the geometric problems under consideration.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Agarwal, L. Guibas, S. Saxe, P. Shor, A linear time algorithm for computing the Voronoi diagram of a convex polygon,Proceedings of the Annual ACM Symposium on Theory of Computing, 1987, pp. 39–45.
N. Alon, E. Gyori, The number of small semispaces of a finite set of points in the plane,J. Combin. Theory Ser. A 41 (1986), 154–157.
K. Brown, Voronoi diagrams from convex hulls,Inform. Process. Lett. 9 (1979), 223–228.
B. Chazelle, H. Edelsbrunner, An improved algorithm for constructingk-th order Voronoi diagram,Proceedings of the Annual Symposium on Computational Geometry, 1985, pp. 228–234.
B. Chazelle, F. Preparata, Halfspace range search: an algorithmic application ofk-sets,Discrete Comput. Geom. 1 (1986), 83–93.
K. Clarkson, New applications of random sampling in computational geometry,Discrete Comput. Geom. 2 (1987), 195–222.
K. Clarkson, Applications of random sampling in computational geometry, II,Proceedings of the Annual Symposium on Computational Geometry, 1988, pp. 1–11.
K. Clarkson, P. Shor, Algorithms for diametral pairs and convex hulls that are optimal randomized, and incremental,Proceedings of the Annual Symposium on Computational Geometry, 1988, pp. 12–17.
R. Cole, M. Sharir, C. Yap, Onk-hulls and related problems,Proceedings of the 16th Annual SIGACT Symposium, 1984, pp. 154–166.
H. Edelsbrunner, Edge skeletons in arrangements with applications,Algorithmica 1 (1986), 93–109.
H. Edelsbrunner, Private communication.
H. Edelsbrunner, J. O'Rourke, R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341–363.
H. Edelsbrunner, R. Seidel, Voronoi diagrams and arrangments,Discrete Comput. Geom. 1 (1986), 25–44.
P. Erdös, L. Lovász, A. Simmons, E. Strauss, Dissection graphs of planar point sets, inA Survey of Combinatorial Theory, J. N. Srivastava,et al., eds., North-Holland, Amsterdam, 1973, pp. 139–149.
J. E. Goodman, R. Pollack, On the number ofk-subsets of a set ofn points in the plane,J. Combin. Theory Ser. A 36 (1984), 101–104.
D. Knuth,The Art of Computer Programming, Vol. 2, Addison Wesley, Reading, MA, 1969.
D. Lee, Onk-nearest neighbour Voronoi diagrams in the plane,IEEE Trans. Comput. 31 (1982), 478–487.
K. Mulmuley, A fast planar partition algorithm, I,Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 580–589. Full version to appear inJ. Symbolic Logic, a special issue on Computational Geometry.
K. Mulmuley, A fast planar partition algorithm, II,Proceedings of the Fifth ACM Annual Symposium on Computational Geometry, 1989, pp. 33–43. To appear inJ. Assoc. Comput. Mach.
K. Mulmuley, An efficient algorithm for hidden surface removal,Computer Graphics 23(3) (1989), 379–388.
K. Mulmuley, An efficient algorithm for hidden surface removal, II, Technical Report, University of Chicago, August 1989, Invited for publication inJ. Algorithms. (Also see On obstructions in relation to a fixed viewpoint,Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 592–597.)
F. Preparata, M. Shamos,Computational Geometry, Springer-Verlag, New York, 1985.
E. Welzl, More onk-sets of finite sets in the plane,Discrete Comput. Geom. 1 (1986), 95–100.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mulmuley, K. On levels in arrangements and voronoi diagrams. Discrete Comput Geom 6, 307–338 (1991). https://doi.org/10.1007/BF02574692
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574692