[2018 Discrete Math 세미나 ]

** Date: ** 2018-03-27

**Speaker :** Antoine Vigneron (UNIST)

**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.

**VOD : **[VIDEO] [YOUTUBE]

Information Center for Mathematical Sciences KAIST

34141 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8196

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2018. ICMS All Rights Reserved.

34141 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8196

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2018. ICMS All Rights Reserved.