08/10/30 16:07:07
>>777
URLﾘﾝｸ(i11www.iti.uni-karlsruhe.de)
のイントロに書いてあるけど，
[CY84]: 前処理 O(n^2)，問い合わせ O(log n)
[LC85]: 前処理 O(n^2)，問い合わせ O(log n)
[MC95]: 前処理 O(n log n)，問い合わせ O(n^0.695)
[Mu03]: 前処理 O(n^1+ε)，問い合わせ O(n^{1/2 + ε})
くらいの結果はあるみたいね．
一通り目を通してみたけど，LC85 は特に簡単．双対変換すると
「直線 l に一番近い点 p」⇔「点 l* の真上にある直線 p*」
という関係になることに注意して，点位置決定問題に帰着するだけ．