# 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)
##### Keywords:
combinatorial complexity; convex polygons; common exterior
Full Text:
##### References:
  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  Aronov, B.; Bern, M.; Eppstein, D., Arrangements of polytopes with applications, (1992), manuscript  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  Aronov, B.; Sharir, M., The union of convex polyhedra in three dimensions, (), 518-527  B. Aronov, M. Sharir and B. Tagansky, The union of convex polyhedra in three dimensions, SIAM J. Comput., to appear. · Zbl 0891.68116  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  Clarkson, K.L.; Shor, P.W., Applications of random sampling in computational geometry II, Discrete comput. geom., 4, 387-421, (1989) · Zbl 0681.68060  Edelsbrunner, H., Algorithms in combinatorial geometry, (1987), Springer Heidelberg · Zbl 0634.52001  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  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  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  Har Peled, S., The complexity of many faces in the overlay of arrangements, ()  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  Katona, G.O., On a problem of L. fejes Tóth, Stud. sci. math. hung., 12, 77-80, (1977) · Zbl 0437.52005  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  Kovalev, M.D., One property of convex sets and its applications, Math. zametki, 44, 89-99, (1988), (in Russian) · Zbl 0652.52003  Matoušek, J., Construction of ϵ-nets, Discrete comput. geom., 5, 427-448, (1990) · Zbl 0701.68040  Sharir, M.; Agarwal, P.K., Davenport-schinzel sequences and their geometric applications, (1995), Cambridge University Press New York · Zbl 0834.68113  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.