원치 않는 점을 제외하기 위해 볼록 선체 수정

내 C# -Silverlight 3 프로그램에서 점 집합이 있습니다. 이러한 포인트는 다른 색상, 녹색, 빨간색 또는 파란색 일 수 있습니다. 그런 다음 다른 점에 대한 볼록 선체를 만듭니다. 녹색 선체, 빨간색 선체 및 파란색 선체. 이제는 각 색상의 선체 내에서 녹색 선체 내의 빨간색 점과 같은 다른 색상의 점이 발생할 수 있습니다.원치 않는 점을 제외하기 위해 볼록 선체 수정

선체를 수정하는 알고리즘이 있습니까? 그러면 다른 색상의 점이 선체에서 제외됩니다 (더 이상 볼록하지 않음). 사전에

감사합니다, 프랭크

출처

2009-10-20 Aaginor

는 제외하여 무엇을 의미합니까 N * 로그 (N)인가? 이 점수를 없앨까요? 그러나 일부 점을 제거하면 기존의 볼록 선체를 "끊을"수 있습니다. 녹색 볼록 선체의 모든 점이 빨간색 볼록 선체 안에 있으면 어떻게됩니까? 이 질문에 답하기 위해서는 더 자세한 정보가 필요합니다. 구체적인 예제도 도움이 될 것입니다. –

볼록 선체를 "파괴"한다는 것은 3 점이 다른 선체 안에 있기 때문에 볼록 선체의 5 점 중 3 점을 제거하는 것을 의미했습니다. 그러면 볼록 선체가 될 수없는 나머지 2 개의 점이 생깁니다. –

고전 외판원 문제 번역.

이 선체를 생성하는 점을 사용하고 제외시키려는 다른 점을 추가하십시오. 이제이 점 이상 shotrest 경로를 찾아이 새로운 선체

EDIT 우리는 포인트를 통해 하나 개의 noncrossing 경로를 찾을 필요가

있습니다.

하면 중앙에 하나 개의 포인트 (예를 들면 산술 (artithmetic) 중심)의 각 점 (사용 함수 ATAN2)에
계산 각도 각도이 점
정렬을 찾는다.

복잡성 지금

출처

2009-10-20 13:42:36

암호로 대답했지만 정확한 결론 : NP 어려운 문제입니다. –

@Clint Tseng 나는 이제 생각하고있다. 한번 제외되면이 배제 된 포인트를 통해 가장 까다로운 길을 찾아야 할 필요는 없다. 그것은 단지 선체가되는 것입니다. 포인트에 대한 비 교차 경로를 찾는 것은 최악의 N * log (N)입니다. –

내가 관심을 보였던 http://research.cs.queensu.ca/home/daver/Pubs/MyPDF/CCMSP_EadesRappaport.pdf가 발견되었습니다. :) –

원치 않는 점을 제외하기 위해 볼록 선체 수정

답변

관련 문제