짐 꾸리기 알고리즘 ( Gift wrapping algorithm )

주제(Subject)
--------------------------------------------------------
한글(약어) : 짐 꾸리기 알고리즘()
영어(약어) : Gift wrapping algorithm()


관련개념(Related Concepts)
--------------------------------------------------------
기하 알고리즘
Computational Geometry


개요(Summary)
--------------------------------------------------------
점(convex)집합이 있을 때, 이들 점을 모두 포함할 수 있는 볼록 껍질을 구하는 방법. Jarvis March라고도 한다.


본문(Body)
--------------------------------------------------------
1. 개념
점 집합의 볼록 껍질을 구하기 위한 방법으로 가장 직관적인 방법. 한 점에서 출발하여, 모든 점을 검사하면서 각도가 가장 작은 점들을 연결하면 볼록 껍질이 구해진다.

2. 시뮬레이션
   (1) 아래 영문 참고문헌 중 3~4번 참고

3. 의사코드

def jarvis(P)
  i = 0
  p[0] = leftmost point of P
  do
    p[i+1] = point such that all other points in P are to the
                                 right of the line p[i]p[i+1]
    i = i + 1
  while p[i] != p[0]
  return p

                                                               Wikipedia:Gift wrapping algorithm

모임,단체(Commutities)
--------------------------------------------------------


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------
1. Tim Lambert (School of Computer Science and Engineering, The University of New South Wales, Sydney 2052, AUSTRALIA)
   http://www.cse.unsw.edu.au/~lambert/


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)
1. 조유근, 홍영식, 이지수, 김명. "알고리즘 - 알고리즘의 설계와 분석". 이한출판사. 2005. (ISBN:89-8241-210-7)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Gift wrapping algorithm
   http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

2. Wikipedia : Convex Hull
   http://en.wikipedia.org/wiki/Convex_hull

3. Jarvis' March(Alejo Hausner:PhD student at Princeton)
   http://www.cs.princeton.edu/~ah/alg_anim/version1/JarvisMarch.html

4. Convex Hull Algorithms (Tim Lambert's Homepage)
   http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

5. Google Search : type [[Gift Wrapping Algorithm]]@google
   http://www.google.com/search?hl=en&q=Gift+wrapping+algorithm