k-Sets and rectilinear crossings in complete uniform hypergraphs

Rahul Gangopadhyay, Saswata Shannigrahi

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

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
ЖурналComputational Geometry: Theory and Applications
Том86
Ранняя дата в режиме онлайн14 окт 2019
DOI
СостояниеОпубликовано - янв 2020

    Fingerprint

Предметные области Scopus

  • Прикладные компьютерные науки
  • Геометрия и топология
  • Теория оптимизации
  • Математика и теория расчета
  • Вычислительная математика

Цитировать