×

zbMATH — the first resource for mathematics

The common exterior of convex polygons in the plane. (English) Zbl 0881.68122
Summary: We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of \(k\) convex polygons in the plane, with a total of \(n\) edges. We show: (1) The maximum complexity of the entire common exterior is \(\Theta(n\alpha(k)+ k^2)\). (2) The maximum complexity of a single cell of the common exterior is \(\Theta(n\alpha(k))\). (3) The complexity of \(m\) distinct cells in the common exterior is \(O(m^{2/3}k^{2/3}\log^{1/3}(k^2/m)+ n\log k)\) and can be \(\Omega(m^{2/3}k^{2/3}+ n\alpha(k))\) in the worst case.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alevizos, P.; Boissonnat, J.D.; Preparata, F.P., An optimal algorithm for the boundary of a cell in a union of rays, Algorithmica, 5, 573-590, (1990) · Zbl 0697.68030
[2] Aronov, B.; Bern, M.; Eppstein, D., Arrangements of polytopes with applications, (1992), manuscript
[3] Aronov, B.; Edelsbrunner, H.; Guibas, L.; Sharir, M., Improved bounds on the number of edges of many faces in arrangements of line segments, Combinatorica, 12, 261-274, (1992) · Zbl 0768.52003
[4] Aronov, B.; Sharir, M., The union of convex polyhedra in three dimensions, (), 518-527
[5] B. Aronov, M. Sharir and B. Tagansky, The union of convex polyhedra in three dimensions, SIAM J. Comput., to appear. · Zbl 0891.68116
[6] Clarkson, K.; Edelsbrunner, H.; Guibas, L.; Sharir, M.; Welzl, E., Combinatorial complexity bounds for arrangements of curves and spheres, Discrete comput. geom., 5, 99-160, (1990) · Zbl 0704.51003
[7] Clarkson, K.L.; Shor, P.W., Applications of random sampling in computational geometry II, Discrete comput. geom., 4, 387-421, (1989) · Zbl 0681.68060
[8] Edelsbrunner, H., Algorithms in combinatorial geometry, (1987), Springer Heidelberg · Zbl 0634.52001
[9] Edelsbrunner, H.; Guibas, L.; Sharir, M., The complexity and construction of many faces in arrangements of lines and of segments, Discrete comput. geom., 5, 161-196, (1990) · Zbl 0691.68035
[10] Edelsbrunner, H.; Welzl, E., On the maximal number of edges of many faces in arrangements, J. comb. theory, ser. A, 41, 159-166, (1986) · Zbl 0585.52002
[11] Guibas, L.; Sharir, M.; Sifrony, S., On the general motion planning problem with two degrees of freedom, Discrete comput. geom., 4, 491-521, (1989) · Zbl 0685.68049
[12] Har Peled, S., The complexity of many faces in the overlay of arrangements, ()
[13] Huttenlocher, D.P.; Kedem, K.; Kleinberg, J., Voronoi diagrams of rigidly moving sets of points, Inform. process. lett., 43, 217-223, (1992) · Zbl 0773.68072
[14] Katona, G.O., On a problem of L. fejes Tóth, Stud. sci. math. hung., 12, 77-80, (1977) · Zbl 0437.52005
[15] Kedem, K.; Livne, R.; Pach, J.; Sharir, M., On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete comput. geom., 1, 59-71, (1986) · Zbl 0594.52004
[16] Kovalev, M.D., One property of convex sets and its applications, Math. zametki, 44, 89-99, (1988), (in Russian) · Zbl 0652.52003
[17] Matoušek, J., Construction of ϵ-nets, Discrete comput. geom., 5, 427-448, (1990) · Zbl 0701.68040
[18] Sharir, M.; Agarwal, P.K., Davenport-schinzel sequences and their geometric applications, (1995), Cambridge University Press New York · Zbl 0834.68113
[19] Wiernik, A.; Sharir, M., Planar realization of non-linear Davenport-schinzel sequences by segments, Discrete comput. geom., 3, 15-47, (1988) · Zbl 0636.68043
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.