作者Favonia (小西风最乖了*^^*)
站内Prob_Solve
标题Re: [问题] 面试问到的问题...
时间Thu Dec 13 00:44:17 2012
用射影几何的对偶变换，原本问题
「给定一堆点求一条穿过最多点的线」
的对偶问题是知名问题
「给定一堆线求一个穿过最多线的点」
唯一要注意的地方是射影平面在我们一般熟知的平面上
加上许多无穷远「理想点」，每一组平行线都会相交於某个
无穷远的「理想点」。这些理想点又形成一条「理想线」。
这些多加的元素让线跟点完全对称。
撇开这些抽象概念，其中一个对应就是把一个点 (a,b)
变成 y = ax + b 这条线。简单来说，通过一个点的所有可
能的直线的参数，在参数平面上会形成一条直线。
给定一堆线求相交的点，应该可以用 Bentley-Ottmann
演算法，只要小心垂直线和完全平行的线就行了。以下我没
有仔细想过，有赖大家验证：参数平面中的垂直线应该是对
应到原来平面中的理想点，大概可以忽略它，因为欧式几何
里面没有理想点。参数平面中的非垂直平行线代表原平面中
相同 a 不同 b 的点... 也就是在原平面中会被垂直线穿过
的点；或用术语来说，这些平行线交於某个理想点，而这个
理想点对应回来就是那条垂直线。
总而言之，如果我上个段落後半部没有想错的话，先考
虑所有垂直线，然後通过对偶在参数平面上用 Bentley-
Ottmann 找交点。全部应该可以在 O(nlgn) 时间内完成。
===
我记错了，Bentley-Ottmann 的复杂度是 O((n+k)lgn)
有其他演算法是 O(nlgn + k). 如果全部要写成 n 那复杂度
还是 O(n^2).
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.39
※ 编辑: Favonia 来自: 140.112.30.39 (12/13 00:46)
※ 编辑: Favonia 来自: 140.112.30.39 (12/13 00:47)
※ 编辑: Favonia 来自: 140.112.30.39 (12/13 19:15)