Polytopes in arrangements
作者： Boris Aronov , Tamal K. Dey
关键词: Hyperplane 、 Polytope 、 Regular polytope 、 Upper and lower bounds 、 Vertex arrangement 、 Polyhedral combinatorics 、 Mathematics 、 Discrete mathematics 、 Discrete geometry 、 Combinatorics 、 Disjoint sets
摘要: Consider an arrangement of n hyperplanes in \real d . Families convex polytopes whose boundaries are contained the union subject this paper. We aim to bound their maximum combinatorial complexity. Exact asymptotic bounds were known for case where cells arrangement. Situations pairwise openly disjoint have also been considered past. However, no nontrivial was general may overlapping interiors, d>2 analyze families that do not share vertices. In 3 we show O(k 1/3 2 ) on number faces k such polytopes. discuss worst-case lower and higher-dimensional versions problem. Among other results, facets vertex-disjoint is Ω(k 1/2 d/2 which a factor $\sqrt{n}$ away from best upper range d-2 ≤ The 1≤ completely resolved as ?(kn) applies here.
core.ac.uk
acm.org
sci-hub.se 参考文章(16)
Dan Halperin, Micha Sharir, Arrangements and their applications in robotics: recent developments workshop on the algorithmic foundations of robotics. pp. 495- 511 ,(1995)
N. Katoh, T. Tokuyama, Lovasz's lemma for the three-dimensional K-level of concave surfaces and its applications foundations of computer science. pp. 389- 398 ,(1999) , 10.1109/SFFCS.1999.814610
Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, The Complexity of Many Cells in Arrangements of Planes and Related Problems ,(2011)
Dan Halperin, Micha Sharir, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom Computational Geometry: Theory and Applications. ,vol. 1, pp. 269- 303 ,(1992) , 10.1016/0925-7721(92)90008-G
T. K. Dey, H. Edelsbrunner, Counting triangle crossings and halving planes Discrete and Computational Geometry. ,vol. 12, pp. 281- 289 ,(1994) , 10.1007/BF02574381
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres Discrete & Computational Geometry. ,vol. 5, pp. 99- 160 ,(1990) , 10.1007/BF02187783
D. Eppstein, Geometric Lower Bounds for Parametric Matroid Optimization Discrete and Computational Geometry. ,vol. 20, pp. 463- 476 ,(1998) , 10.1007/PL00009396
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
Pankaj K. Agarwal, Boris Aronov, Counting facets and incidences Discrete & Computational Geometry. ,vol. 7, pp. 359- 369 ,(1992) , 10.1007/BF02187848
Boris Aronov, Jir̆í Matous̆ek, Micha Sharir, On the sum of squares of cell complexities in hyperplane arrangements Journal of Combinatorial Theory, Series A. ,vol. 65, pp. 311- 321 ,(1994) , 10.1016/0097-3165(94)90027-2