$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
안녕하세요!
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보

선분가시 다각형 내부에 있는 두 점 사이의 최단 경로를 구하는 빠른 알고리즘

A Fast Shortest Path Algorithm Between Two Points inside a Segment-Visible Polygon

초록

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

Abstract

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. 

이 논문을 인용한 문헌 (0)

  1. 이 논문을 인용한 문헌 없음

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

상세조회 0건 원문조회 0건

DOI 인용 스타일