미술관 정리 및 알고리즘

미술관 이론과 알고리즘은 미술관 문제와 관련된 주제, 박물관의 모든 지점이 적어도 한 명의 경비원이 볼 수 있도록 다각형 박물관 평면 내에서 경비원의 위치를 찾는 것, 그리고 다각형에 관한 계산 기하학의 관련 문제에 관한 수학적인 단문이다.조셉 오루크가 저술했으며, 1987년 옥스퍼드 대학 출판부의 컴퓨터 과학에 관한 국제 모노그래프 시리즈에 실렸다.^{[1][2][3][4][5]}책이 절판되기 전에 겨우 1000부만 제작되었기 때문에, 이 자료를 이용할 수 있는 오루크는 이 책의 pdf 버전을 온라인에서 사용할 수 있게 만들었다.^[6]

주제

1973년 빅토르 클리가 제기한 미술관 문제는 폴리곤(박물관의 평면도를 나타냄) 내부에 가드를 배치하여 폴리곤 내의 각 포인트가 적어도 한 명의 가드에게 보이도록 하는 포인트 수를 요구한다.Václav Chvátal은 답안이 n ${\displaystyle n}$ 모서리가$$ $있는{\displaystyle }$ 폴리곤에 대해$$ ${\displaystyle \mathrm{most}}$n / ${\displaystyle 3\mathrm{}}$⌉ ${\displaystyle \lceil n/3\rceil }$이라는 첫 번째 증거를 제공했지만, 그래프 컬러링과 폴리곤 삼각측정에 기초한 Steve Fisk의 간단한 증거는 더 널리 알려져 있다.하고 가시성, 다각형의 decompositions, 다각형 triangulations과 삼각점 알고리즘의 모자 및 결과는 Schönhardt 다면체 같은 다면체 추가 없이 triangulations을 가지고 있지 않아 포함한higher-dimensional generalizations,[1]을 포함한 표지 주제에 다니는 book,[3]의 이 여는 물질이다.ition정점^[1][4]보다 일반적으로, 이 책은 "분리 기하학과 계산 기하학의 상호 작용"^[3]을 주제로 하고 있다.

이 책은 10개의 장으로 구성되어 있는데, 이 장들의 주제는 원래의 미술관 정리 및 피스크의 삼각측량 기반 증명, 직선으로 된 다각형, 한 점보다는 선 구획을 순찰할 수 있는 가드, 항성형 다각형, 나선형 다각형, 모노톤 다각형을 포함한 다각형의 특수 계급, 단순하지 않은 다각형, 감옥 마당 문제 등이다.h 가드는 다각형의 외부 또는 내부와 외부 모두를 보아야 한다. 가시성 그래프, 가시성 알고리즘, 가드 수를 최소화하기 위한 계산 복잡성, 3차원 일반화.^[2][3]

청중 및 접대

이 책은 그래프 이론과 알고리즘에 대한 학부 수준의 지식만을 필요로 한다.^[2]그러나 연습이 부족하고, 교과서보다는 모노그래프로 편성되어 있다.^[5]기술하는 알고리즘의 구현자에게 중요할 수 있는 일부 세부사항을 생략하고 최악의 복잡성이 심각함에도 불구하고 무작위 입력에서 우수한 성능을 발휘하는 알고리즘을 설명하지 않는다는 경고에도 불구하고 검토자 Wm은 검토자 Wm랜돌프 프랭클린은 그것을 "모든 지오미터의 라이브러리를 위해" 추천한다.^[4]

리뷰어 허버트 에델스브루너(Herbert Edelsbrunner)는 "이 책은 현재 이용할 수 있는 폴리곤에 대한 결과의 가장 포괄적인 모음집이며, 따라서 계산 기하학에서 표준 텍스트로서의 지위를 획득한다"고 쓰고 있다.매우 잘 쓰여져 있고 읽는 것도 즐겁다고 말했다.^[1]그러나, 리뷰어 Patrick J. Ryan은 이 책의 일부 증명들이 부적절하다고 불평하고,^[5] 1990년에 쓴 리뷰어 David Avis는 그 무렵 이미 이 책을 시대에 뒤떨어지게 만드는 "많은 새로운 발전"이 있었다고 언급했다.그럼에도 불구하고 에이비스는 학부생이나 다른 분야의 연구자들을 위한 입문서로, 그리고 이 부분에 남아 있는 '미해결 문제 많은 것'을 풀기 위한 초대장으로서 '여러 가지 차원에서 책이 성공한다'고 쓰고 있다.^[3]

참조