×

The complexity of cutting complexes. (English) Zbl 0663.68055

This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross- section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.

MSC:

68Q25 Analysis of algorithms and problem complexity
68U99 Computing methodologies and applications
52A37 Other problems of combinatorial convexity
52A10 Convex sets in \(2\) dimensions (including convex curves)
52A15 Convex sets in \(3\) dimensions (including convex surfaces)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Connelly, R. and Henderson, D. W., A convex 3-complex is not simplicially isomorphic to a strictly convex complex,Math. Proc. Cambridge Philos. Soc.88 (1980), 299-306. · Zbl 0449.52004 · doi:10.1017/S0305004100057595
[2] Edelsbrunner, H.,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[3] Edelsbrunner, H. and Guibas, L. J., Topologically sweeping an arrangement, Tech. Rep. 9, DEC/SRC, April 1986. Also,Proc. 18th STOC, 1986, pp. 389-403. · Zbl 0676.68013
[4] Grünbaum, B.,Convex Polytopes, Wiley, New York, 1967. · Zbl 0163.16603
[5] Guibas, L. J. and Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,ACM Trans. Graphics4 (1985), 75-123. · Zbl 0586.68059 · doi:10.1145/282918.282923
[6] Guibas, L. J.; Yao, F. F.; Preparata, F. P. (ed.), On translating a set of rectangles, 61-77 (1983), Greenwich, CT
[7] Hall, M.,Combinatorial Theory, Blaisdell, Waltham, MA, 1967. · Zbl 0196.02401
[8] Moser, W. and Pach, J., Research Problems in Discrete Geometry, Manuscript, 1986. · Zbl 1086.52001
[9] Zaslavsky, Th., Facing up to arrangements: face-count formulas for partitions of space by hyperplanes,Mem. Amer. Math. Soc.154 (1975), 1-71. · Zbl 0296.50010
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.