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.

Original languageEnglish
Article number101578
Number of pages7
JournalComputational Geometry: Theory and Applications
Volume86
Early online date14 Oct 2019
DOIs
StatePublished - Jan 2020

    Research areas

  • Affine Gale diagram, Balanced line, Gale transform, k-Set, Rectilinear crossing number, NUMBER

    Scopus subject areas

  • Computational Mathematics
  • Control and Optimization
  • Geometry and Topology
  • Computer Science Applications
  • Computational Theory and Mathematics

ID: 49848807