Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
In this paper, we study the d-dimensional rectilinear drawings of the complete d-uniform hypergraph K2d d. Anshu et al. (2017) [3] used Gale transform and Ham-Sandwich theorem to prove that there exist Ω(2d) crossing pairs of hyperedges in such a drawing of K2d d. We improve this lower bound by showing that there exist Ω(2dd) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d. We also prove the following results. 1. There are Ω(2dd3/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices are either not in convex position in Rd or form the vertices of a d-dimensional convex polytope that is t-neighborly but not (t+1)-neighborly for some constant t≥1 independent of d. 2. There are Ω(2dd5/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices form the vertices of a d-dimensional convex polytope that is (⌊d/2⌋−t′)-neighborly for some constant t′≥0 independent of d.
Язык оригинала | английский |
---|---|
Номер статьи | 101578 |
Число страниц | 7 |
Журнал | Computational Geometry: Theory and Applications |
Том | 86 |
Дата раннего онлайн-доступа | 14 окт 2019 |
DOI | |
Состояние | Опубликовано - янв 2020 |
ID: 49848807