Archive of posts with tag 'AntoineVigneron'

• Antoine Vigneron, Reachability in a Planar Subdivision with Direction Constraints

  Reachability in a Planar Subdivision with Direction Constraints

  Antoine Vigneron
  School of Electrical and Computer Engineering, UNIST, Ulsan, South Korea

  2018/3/27 Tue 5PM

  Given a planar subdivision with n vertices, each face having a cone of possible directions of travel, our goal is to decide which vertices of the subdivision can be reached from a given starting point s. We give an O(n log n)-time algorithm for this problem, as well as an Ω(n log n) lower bound in the algebraic computation tree model. We prove that the generalization where two cones of directions per face are allowed is NP-hard.

  Tags:

  • AntoineVigneron

• Antoine Vigneron, A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space

  A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space

  Antoine Vigneron
  KAUST, Kingdom of Saudi Arabia

  2014/03/31 Monday 4PM-5PM
  Room 1409

  We show that the Gromov hyperbolicity of a discrete metric space at a fixed base-point cannot be computed in O(n^2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication algorithm than is currently known.

  Tags:

  • AntoineVigneron