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

논문 상세정보

점 집합을 두 개의 부채꼴로 포함하는 알고리즘 개발
Algorithms for Covering a Point Set with Two Wedges

김성권   (중앙대학교 컴퓨터공학과UU0001197  ); 김순석   (중앙대학교 컴퓨터공학과UU0001197  ); 신찬수   (한국과학기술원 전산학과 BK21UU0001375  ); 여상수   (중앙대학교 컴퓨터공학과UU0001197  );
  • 초록

    평면상의 n 개의 점으로 구성된 집합 S가 있을 때, 같은 각의 두 (무한) 부채꼴을 이용하여 S의 점들을 모두 포함하는 문제를 본 논문에서 다루고자 한다. 즉, S W $_1$ ∪W $_2$ 를 만족하는 각이 최소인 두 부채꼴 W $_1$ 과 W $_2$ 를 구하고자 한다. 부채꼴의 정점은 반드시 S의 점에만 놓는다. 두 부채꼴의 배치에 ek라서 여러 가지 경우로 나눌 수 있는데 각 경우에 효율적인 알고리즘을 제시한다.


  • 참고문헌 (11)

    1. J.W. Jaromczyk and M. Kowaluk, Orientation independent covering of points in $R^2$ with pairs of rectangles, Lecture Notes in Computer Science, vol. 871, pp. 71-78, 1996 
    2. M.J. Katz, K. Kedem, and M. Segal, Discrete rectilinear 2-center problems, Computational Geometry, vol. 15, pp. 203-214, 2000 
    3. M. Sharir, A near-linear algorithm for the planar 2-center problem, Proceedings of 12th Annual ACM Symposium on Computational Geometry, pp. 106-112, 1996 
    4. P.K. Agarwal, M. Sharir and E. Welzl, The discrete 2-center problem, Proceedings of 13th Annual Symposium on Computational Geometry, pp. 147-155, 1997 
    5. D. Eppstein, Faster construction of planar two-centers, Proceedings of 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 131-138, 1997 
    6. R. Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of ACM, 34, pp. 200-208, 1987 
    7. J. Friedman, J. Hershberger, and J. Snoeyink, Efficiently planning compliant motion in the plane, SIAM Journal on Computing, vol. 25, no. 3, pp. 562-599, 1996 
    8. N. Megiddo, Applying parallel computing algorithms in the design of serial algorithms, Journal of ACM, vol. 30, pp. 852-865, 1983 
    9. M. H. Overmars and J. van Leeuwen, Maintenance of configurations in the plane, Journal of Computer and System Science, vol. 23, pp. 166-204, 1981 
    10. F.P. Preparata and M.I. Shamos, Computational Geometry: an Introduction, Springer-Verlag, New York, 1985 
    11. P.K. Agarwal and M. Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys, vol. 30, pp. 412-458, 1998 

 저자의 다른 논문

  • 김성권 (19)

    1. 2000 "전광 트리 네트워크에서 파장 및 경로설정 문제를 해결하는 알고리즘에 관한 연구" 정보처리논문지 = The transactions of the Korea Information Processing Society 7 (12): 3952~3963    
    2. 2000 "실용적이고 안전한 전자투표 프로토콜에 관한 연구" 通信情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 10 (4): 21~32    
    3. 2000 "적은 굴곡점을 가진 이진트리를 그리는 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (2): 209~215    
    4. 2000 "두개의 동일한 탐조등으로 볼록다각형을 비추는 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (4): 416~419    
    5. 2001 "디지털 컨텐츠의 지적 재산권 보호를 위한 익명 핑거프린팅의 연구 동향" 情報保護學會誌 = KIISC review 11 (3): 90~99    
    6. 2002 "인터넷 광고에서 안전하고 효율적인 측정방법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (3): 153~160    
    7. 2002 "단백질 시퀀스와 가중치 스트링에 대한 탐색 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (8): 456~462    
    8. 2002 "크로스 링크된 단백질 서브시퀀스를 찾는 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (9): 514~519    
    9. 2003 "이동통신 환경에서 임시 익명 아이디를 이용한 위치 불추적 서비스와 지불 프로토콜에 관한 연구" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (2): 78~92    
    10. 2003 "DNA 마이크로어레이 데이타의 클러스터링 알고리즘 및 도구 개발" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (10): 544~555    
  • 여상수 (5)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

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

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

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

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