Title    name
2018 Discrete Math 세미나
 
  Title
  Speaker Antoine Vigneron
  Date 2018-03-27
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.
 
Abstract : 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.