An Algorithm for Illuminating a Convex Polygon with Two Equal Floodlights

An Algorithm for Illuminating a Convex Polygon with Two Equal Floodlights
An Algorithm for Illuminating a Convex Polygon with Two Equal Floodlights

ㆍ 저자명: 김성권,신찬수,Kim. Sung-Kwon,Shin. Chan-Su
ㆍ 간행물명: 정보과학회논문지. Journal of KIISE. 시스템 및 이론
ㆍ 권/호정보: 2000년|27권 4호|pp.416-419 (4 pages)
ㆍ 발행정보: 한국정보과학회
ㆍ 파일정보: 정기간행물|ENG|
PDF텍스트
ㆍ 주제분야: 기타

이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.

서지반출

영문초록

G를 꼭지점들이 일반 위치에 있는 n개의 꼭지점을 갖는 볼록다각형이라 하자. 본 논문에서는 두 개의 탐조등을 G의 경계선에 배치하여 G의 내부를 모두 비추는 알고리즘을 개발하는데, 두 탐조등의 최대각을 최소화하는 것이 목적이다. 확장된 real-RAM상에서 O($n^2$) 시간 알고리즘을 제시한다

기타언어초록

Let G be an n-vertex convex polygon whose vertices are in general position. We consider an illumination problem of locating two floodlights on the boundary of G, which illuminates G and whose larger angle is as small as possible. We present an O($n^2$) time algorithm under the extended real-RAM model.

다운URL