如果我在坐标系中给出100个点，我必须找到这些顶点中是否存在直角三角形 . 有没有办法可以检测这些顶点中的直角三角形，而不必选择所有3个顶点对，然后在它们上应用毕达哥拉斯定理？可以有更好的算法吗？谢谢你的帮助 . :)
这是 two dimensions only 的 O(n^2 log n)-time 算法 . 我将描述更高维度出了什么问题 .
设S是具有整数坐标的点集 . 对于S中的每个点o，构造一组非零向量V（o）= {p - o | p在S - }中测试V（o）是否在线性时间内包含两个正交向量，如下所示 .
方法1：将每个向量（x，y）册选为（x / gcd（x，y），y / gcd（x，y）），其中| gcd（x，y）|是除x和y之间的最大整数，如果y为负，则gcd（x，y）为负，如果y为正，则为正，| x |如果y为零 . （这非常类似于将一个分数置于最低项中 . ）关于两个维度的关键事实是，对于每个非零向量，恰好存在与该向量正交的一个规范向量，具体地，（ - y，x）的经典化 . 将V（o）中每个向量的标准化插入到集合数据结构中，然后，对于V（o）中的每个向量，在该数据结构中查找其规范的正交配对 . 我假设gcd和/或set操作花费时间O（log n） .
方法2：在向量上定义比较器，如下所示 . 给定向量 (a, b), (c, d) ，当且仅当if时，写 (a, b) < (c, d)
(a, b), (c, d)
(a, b) < (c, d)
s1 s2 (a d - b c) < 0,
哪里
s1 = -1 if b < 0 or (b == 0 and a < 0) 1 otherwise s2 = -1 if d < 0 or (d == 0 and c < 0) 1 otherwise.
使用此比较器对矢量进行排序 . （这与将 a/b 与 c/d 进行比较非常相似 . ）对于V（o）中的每个向量（x，y），二进制搜索其正交配对（-y，x） .
a/b
c/d
在三维中，沿着z轴与单位矢量正交的矢量集是整个x-y平面，并且相位的标准化不能将该平面中的所有矢量映射到一个正交配合 .
1 回答
这是 two dimensions only 的 O(n^2 log n)-time 算法 . 我将描述更高维度出了什么问题 .
设S是具有整数坐标的点集 . 对于S中的每个点o，构造一组非零向量V（o）= {p - o | p在S - }中测试V（o）是否在线性时间内包含两个正交向量，如下所示 .
方法1：将每个向量（x，y）册选为（x / gcd（x，y），y / gcd（x，y）），其中| gcd（x，y）|是除x和y之间的最大整数，如果y为负，则gcd（x，y）为负，如果y为正，则为正，| x |如果y为零 . （这非常类似于将一个分数置于最低项中 . ）关于两个维度的关键事实是，对于每个非零向量，恰好存在与该向量正交的一个规范向量，具体地，（ - y，x）的经典化 . 将V（o）中每个向量的标准化插入到集合数据结构中，然后，对于V（o）中的每个向量，在该数据结构中查找其规范的正交配对 . 我假设gcd和/或set操作花费时间O（log n） .
方法2：在向量上定义比较器，如下所示 . 给定向量
(a, b), (c, d)，当且仅当if时，写(a, b) < (c, d)哪里
使用此比较器对矢量进行排序 . （这与将
a/b与c/d进行比较非常相似 . ）对于V（o）中的每个向量（x，y），二进制搜索其正交配对（-y，x） .在三维中，沿着z轴与单位矢量正交的矢量集是整个x-y平面，并且相位的标准化不能将该平面中的所有矢量映射到一个正交配合 .