3
전산 기하학에서 라인 교차 및 라인 정렬 문제에 대한 문헌을 간략하게 검토했습니다. 대부분은 비행기 스윕 알고리즘을 기반으로합니다. 계산상의 복잡성에 비추어 볼 때, 점근 적 알고리즘 경계는 선분의 수와 "k"라는 용어가 가장자리 사이의 교차점 수인 함수입니다. 예를 들어, 가장 잘 알려진 알고리즘 중 하나는 O (nlogn + "k")의 시간 복잡도를 가지며 출력에 민감합니다. 문제는 시간 복잡성을 제공하면서 왜 "k"라는 용어를 없앨 수 없는지에 대한 이해가 어렵다는 것입니다. 예를 들어 문제를 분류하기위한 다른 알고리즘을 살펴보면 복잡성은 얼마나 많은 스왑 또는 비교가 수행되는지의 함수가 아니기 때문입니다. 이것은 단순히 입력의 수의 함수입니다. 모든 통찰력이 도움이 될 것입니다.라인 세그먼트 또는 에지 교차점 찾기 알고리즘의 시간 복잡도