Computing a Center-Transversal Line

Toni Sellares


A center-transversal line for two finite point sets in three dimensions is a line with the property that any closed halfspace that contains it has at least one third of each point set inside. A center-transversal line always exists, and we provide an algorithm that finds a center-transversal line. Algorithms that find a deepest line, and find an almost-deepest line are also presented.

Joint work with

  • Sergio Cabello, Dep of Math, IMFM, Ljubljana, Slovenia
  • Micha Sharir, School of Computer Science, Tel Aviv University, Israel.