一种O(n * log(n))算法，以找到斜率最低的段(在n * n个段中) [英] A O(n*log(n)) algorithm to find the segment (among n*n segments) with the lowest slope

问题描述

给出 P = {p ₁ ，...，p _n } 2 行，编写一种算法，该算法以最差的时间找到 O(n * log(n))的时间，找到斜率最低(绝对值最小)的线情况.

Given P={p₁,...,p_n} of different points which define n² lines, write an algorithm that finds the line which has the lowest slope (smallest absolute value) with O(n*log(n)) time complexity in the worst case.

推荐答案

定理:

• 给出一组点P.
• 选择P中的两个点A和C，以使AC线具有最小的绝对斜率(如问题中所定义).
• 对于多对点具有相同斜率的简并情况，令AC为具有该斜率的最短线段.
• 然后，P中没有其他点，且Y坐标在A和C之间.

证明(矛盾):

• 假设至少还有一个点B，其Y坐标在A和C之间.
• 然后存在三种可能的情况:
  • B与A和C共线.然后，线AB或BC与AC具有相同的斜率，但它们的 都比AC短.矛盾.
  B落在"AC"上方的半平面中.那么，线AB具有比AC更浅的斜率.矛盾.B落在"AC"下方的半平面中.则线BC的斜率比AC的斜率小.矛盾.
  • Suppose there is at least one other point, B, whose Y-coordinate is between A and C.
  • Then there exist three possible cases:
    • B is co-linear with A and C. Then the lines AB or BC have the same slope as AC, but both of them are shorter than AC. Contradiction.
    • B falls in the half-plane "above" AC. Then the line AB has a shallower slope than AC. Contradiction.
    • B falls in the half-plane "below" AC. Then the line BC has a shallower slope than AC. Contradiction.

    有了这个定理，您可以清楚地使用@Zshazz的算法在 O(n * log n)中找到正确的对-因为它们将是最近的邻居.

    With this theorem, you can clearly use @Zshazz's algorithm to find the correct pair--because they will be nearest neighbors--in O(n*log n).

    这篇关于一种O(n * log(n))算法，以找到斜率最低的段(在n * n个段中)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！