점프 앤 워크 알고리즘

점프 앤 워크(Jump-and-Walk)는 삼각측량에서의 점 위치 알고리즘이다(원론적 분석의 대부분은 2D와 3D 랜덤 델로나이 삼각측량에서 수행되었다).놀랍게도, 알고리즘은 삼각측량 자체의 간단한 표현을 제외하고는 어떤 사전 처리나 복잡한 데이터 구조도 필요로 하지 않는다.점프앤워크의 전신인 로슨(1977년)과 그린·시브슨(1978년)은 무작위 출발점 S를 선택한 뒤 S에서 한 번에 한 삼각형씩 쿼리 지점 Q를 향해 걸어가는 로슨(1978년) 덕분이었다.그러나 이러한 전임자들에 대한 이론적 분석은 1990년대 중반 이후까지 알려져 있지 않았다.

점프 앤 워크는 작은 샘플 포인트 그룹을 선택하고 Q에 가장 가까운 샘플 포인트에서 Q가 포함된 심플렉스가 발견될 때까지 걷기를 시작한다.알고리즘은 얼마간 실용적으로 민속적이었으며, 2D 랜덤 들라우나이 삼각측정에 대한 알고리즘의 공식 발표와 그 성능 분석은 1990년대 중반 데브로예, 뮤케, 주(Ju)에 의해 이루어졌다(논문은 알고리즘리카, 1998년에 나타났다).3D 랜덤 들라우나이 삼각측정에 대한 분석은 뮤케, 사이아스, 주(ACM Symposium of Computing Geometry, 1996)가 맡았다.두 경우 모두 경계 조건을 가정하였는데, 즉 Q는 무작위 델라나이 삼각측정의 정점이 그려지는 볼록 영역의 경계에서 약간 떨어져 있어야 한다.2004년에 Devroye, Lemaire, Moreau는 2D에서 경계 조건을 철회할 수 있다는 것을 보여주었다(논문은 Computing Geometric에 나타났다:이론과 응용, 2004).

점프 앤 워크는 QHUL, Triangle, CGAL과 같은 많은 유명한 소프트웨어 패키지에 사용되어 왔다.

참조

• Green, P. J.; Sibson, R. (1978), "Computing Dirichlet tessellations in the plane", The Computer Journal, 21 (2): 168–173, doi:10.1093/comjnl/21.2.168, MR 0485467.
• Lawson, C. (1977), "Software for C1 surface interpolation", in Rice, J. R. (ed.), Mathematical Software III, NY: Academic Press, pp. 161–194.
• Devroye, Luc; Lemaire, Christophe; Moreau, Jean-Michel (2004), "Expected time analysis for Delaunay point location", Computational Geometry: Theory and Applications, 29 (2): 61–89, doi:10.1016/j.comgeo.2004.02.002, MR 2082208.
• Devroye, L.; Mücke, E. P.; Zhu, Binhai (1998), "A note on point location in Delaunay triangulations of random points", Algorithmica, 22 (4): 477–482, CiteSeerX 10.1.1.15.8612, doi:10.1007/PL00009234, MR 1701623.
• Mücke, 에른스트 P.;Saias, 이삭은 주룽지 총리, 빈하이(1999년), 12일 ACM심포지움에 기하학에(필라델피아 펜실베니아 랑카스터, 1996), 해석 기하학에"처럼 평면 그리고 입체 들로네 triangulations에 전처리 없이 지점 위치 한", 특별한 문제:.이론과 응용 프로그램을 12(1–2):63–83, doi:10.1016(98)00035-2, MR1677599.