본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

선분가시 다각형 내부에 있는 두 점 사이의 최단 경로를 구하는 빠른 알고리즘
A Fast Shortest Path Algorithm Between Two Points inside a Segment-Visible Polygon

김수환    (부산외국어대학교 임베디드IT학과  );
  • 초록

    다각형 내부에 위치한 두 점 사이의 최단 경로는 다각형의 외부를 지나지 않는 경로 중에서 길이가 가장 짧은 경로를 말한다. 일반적인 단순 다각형에서 최단 경로를 구하는 선형 시간 알고리즘은 매우 복잡한 과정으로 알려진 삼각분할을 전처리과정으로 수행해야 한다. 따라서 이론적으로는 최적인 시간복잡도를 갖지만, 실제적으로는 구현이 어려울 뿐만 아니라 입력의 크기가 매우 크지 않은 한 수행 시간이 효율적이지 못하다. 본 논문에서는 다각형 내부의 모든 점들을 볼 수 있는 선분이 존재하는 다각형 부류인 선분가시 다각형의 내부에 위치한 두 점 사이의 최단 경로를 구하는 선형 시간 알고리즘을 제시한다. 이 알고리즘은 삼각 분할을 필요로 하지 않으며, 볼록 외피 구축 등 단순한 절차만으로 구성되어 있어 구현이 용이할 뿐만 아니라 수행 속도도 빠르다


    The shortest path between two points inside a simple polygon P is a minimum-length path among all paths connecting them which don't pass by the exterior of P. A linear time algorithm for computing the shortest path in a general simple polygon requires triangulating a polygon as preprocessing. The linear time triangulating is known to very complex to understand and implement it. It is also inefficient in case that the input without very large size is given because its time complexity has a big constant factor. In this paper, we present the customized shortest path algorithm for a segment-visible polygon which is a simple polygon weakly visible from an internal line segment. Our algorithm doesn't require triangulating as preprocessing and consists of simple procedures such as construction of convex hulls, so it is easy to implement and runs very fast in linear time.


  • 주제어

    가시성 .   선분가시 다각형 .   최단 경로 .   볼록 외피.  

  • 참고문헌 (9)

    1. S.-Q. Xin and G.-J. Wang, "Efficiently Determining a Locally Exact Shortest Path on Polyhedral Surfaces," Computer-Aided Design, Vol. 39, No. 12, pp. 1081-1090, 2007. 
    2. R. Khosravi and M. Ghodsi, "Shortest Paths in Simple Polygons with Polygon-Meet Constraints," Information Processing Letters, Vol. 91, No. 4, pp. 171-176, 2004. 
    3. L. Guibas, J. Hershberger, D. Leven, M. Shrir, and R. Tarjan, "Linear Time Algorithm for Visibility and Shortest Path Problems inside Triangulated Simple Polygons," Algorithmica, Vol. 2, No. 1-4, pp. 209-233, 1987. 
    4. B. Chazelle, "Triangulating a Simple Polygon in Linear Time," Discrete Comput. Geom., Vol. 6, No. 1, pp. 485-524, 1991. 
    5. J. O'rourke, Art Gallery Theorems and Algorithms, Oxford Univ. Press, 1987. 
    6. B. K. Bhattacharya, G. Das, A. Mukhopadhyay, and G. arasimhan, "Optimally Computing a Shortest Weakly Visible Line Segment inside a Simple Polygon," Compur. Geom. Theory and Applications, Vol. 23, No. 1, pp. 1-29, 2002. 
    7. R. L. Graham, "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set," Inform. Process. Lett., Vol. 1, No. 4, pp. 132-133, 1972. 
    8. F.P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985. 
    9. R. Inkulu and S. Kapoor, "Planar Rectilinear Shortest Path Computation Using Corridors," Computational Geometry, Vol 42, No. 9, pp. 873-884, 2009. 

 저자의 다른 논문

  • 김수환 (10)

    1. 1999 "다각형 교차 문제를 위한 상수 시간 재구성메쉬 알고리즘" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (11): 1344~1352    
    2. 2002 "단순 다각형의 두 에지 사이의 가시성 판별을 위한 상수 시간 RMESH 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (12): 640~647    
    3. 2004 "단순 다각형 내부의 두 가시성 다각형에 대한 집합 연산을 수행하는 최적 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (1): 102~111    
    4. 2006 "조명 변화에 강인한 얼굴 검출을 위한 좌우대칭 평균화와 단순회귀분석 보정기법" 한국콘텐츠학회논문지 = The Journal of the Korea Contents Association 6 (12): 21~28    
    5. 2006 "조명 변화에 강인한 얼굴 검출을 위한 좌우대칭 평균화 기법" 게임&엔터테인먼트 논문지= Journal of game & entertainment 2 (2): 45~50    
    6. 2007 "학부 문제해결기법 교과목의 운영 사례" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 25 (7): 21~25    
    7. 2016 "두 가시성 다각형의 교집합과 합집합을 구하는 효율적인 RMESH 알고리즘" 한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering 20 (2): 401~407    
    8. 2017 "광선 슈팅 문제를 위한 볼록 레이어 트리" 한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering 21 (4): 753~758    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기