| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1997년05월26일(월) 11시57분42초 KDT 제 목(Title): [Re] [문제] 갤러리 5명짜리 겔러리... _ _ _ _ _ |*|_|*|_|*|_|*|_|*| |_________________| _ |*|__ |__ *| | |__ |__ *| | |__ |__ *| | |__ |__ *| |_| 6명짜리도 있나?? hole이 없고, 직각이란 조건이 빠지면 6명이 lower bound인건 맞는데... (n/3 의 floor값!) 에공... 이건 rectilinear polygon의 minumum watchman의 lower bound 문제군.. 누군가가 이미 잘 정리해놓았을텐데... 찾아보니 n/4의 floor가 맞습니다. 따라서 5명이 lower bound네요. 이 문제는 Art Gallery problem 또는 Watchman problem이라고 해서 Computational Geometry 에서 다루는 유명한 문제중의 하나입니다. -- 박종대 |