On X-raying convex polytopes in small dimensions

Project Leader

Graduate Mentor

  • Federico Firoozi

Problem Statement

Let $K$ be a convex body in $d$-dimensional Euclidean space, that is, a compact convex set with non-empty interior. Let $L$ be a line through the origin. We say that the point $p$ of $K$ is X-rayed along $L$ if the line parallel to $L$ passing through $p$ intersects the interior of $K$. The X-ray number of $K$ is the smallest number of lines through the origin such that every point of $K$ is X-rayed along at least one of these lines.

In 1994, Bezdek and Zamfirescu published the conjecture – often called the X-ray Conjecture – that the X-ray number of any convex body in $d$-dimensional Euclidean space is at most $3.2^{d-2}$. The X-ray conjecture is proved in the plane and it is open in any dimension higher. Here we propose to investigate the following problem, which is strongly connected to the X-ray conjecture. In order to state it we need to recall the following concepts from the theory of convex polytopes. The convex polytope $P$ is called weakly neighborly if any two vertices of $P$ lie on a face of $P$. Furthermore, the convex polytope $P$ is called antipodal if any two vertices of $P$ lie on parallel supporting hyperplanes of $P$. Conjecture [Bezdek and Kiss (2009)]. If $P$ is an arbitrary $d$-dimensional weakly neighborly antipodal convex polytope, then the number of vertices of $P$ is at most $3(2^{d-2})$ for all $d>2$.

If the above conjecture holds, then it proves the X-ray conjecture for the family of weakly neighborly antipodal convex polytopes (and the upper bound is sharp). On the other hand, if it fails, then it generates a counter-example to the X-ray Conjecture. Thus, it would be very timely to prove or disprove the Bezdek-Kiss Conjecture. In fact, in dimensions 3 and 4, one would expect a computational approach by characterizing, that is, listing the different combinatorial (resp., geometric) types of weakly neighborly antipodal convex polytopes. Hence, one is left with checking the Bezdek-Kiss conjecture for those specific combinatorial-geometric classes of convex polytopes.

Final Report


  • Expected team size: 2
  • Student Experience Level: Intermediate: students who have an introduction to proofs
  • Linear Algebra
  • Analysis
  • combinatorics and/or graph theory
  • Maple or Matematica or similar
Károly Bezdek
Károly Bezdek
Professor of Mathematics, Canada Research Chair (Tier 1) in Computational and Discrete Geometry