stable maintainance of point set triagulization in two dimensions Steven Fortune. 1989

を読んだメモ

イントロ

  • ε-算術
  • ロバスト：計算結果が、入力の摂動に対する答えになっている
  • 安定：その摂動が小さい
  • 幾何アルゴリズムが安定という主張は、数値計算において問題の条件数が小さい、という主張のアナログになっている。どちらも、後ろ向きの誤差評価で評価できるらしい
  • 2つのアルゴリズムが示される。1つめが凸包
  • メインの主張は、点群の三角化（triangulation）が安定に扱えること
    • point-location？
    • 追加
    • 削除
    • 凸な四角形をなす三角形の対角線の交換 後半の主張は関係ないから飛ばす（そっちがメインなのに・・）
  • すでに行った比較から答えが確定する比較を行わないアルゴリズムを「ケチ」という
  • ケチなアルゴリズムは、常にロバスト。アルゴリズムをロバストにするのにケチにするのは自明な方法

α-predicate

P：predicateの時、次を満たすような判定関数をP~のα-predicateという

  • P(g) ⇒ P~(g)：Pよりも緩い条件
  • P~(g) ⇒ gのすぐ近くのg’でP(g)となるものが存在 つまり、P~(g)を満たすgの集合は、「Pより大きいが、大きすぎない」

ε-arithmetic test

あるプログラムCodePが、α-predicate のペアP~, Q~に対して、次の条件をみたすときε-arithmetic testという

  • CodeP(x) ⇒ P~
  • not CodeP(x) ⇒ Q~ P~とQ~としては、正確な排反にはならず、重なった部分で曖昧な結果となるようなものを考える。

ε-arithmetic testは、間違った判定をしてしまうかもしれないが大きく間違うことはない、という判定器を表現している（例えば数値の正負を判定を考えると、仮に実際と違う判定になったとしても、その場合には値の絶対値は極めて小さい、というような感じ）

角度

  • ∠abcで、b→aからb→cに向かった左回りの角度・あるいは方向を表す
  • μabcで、↑の角度を表す（mod 2πで）

ほとんど正の三角形

ここの定義が曖昧でむずかしい。 μbac, μcba, μbcaが[-δ, π+δ]の範囲にあるとき、△abcはほとんど正という。

  • bac, cbaは同じ向きに角度を測っているが、bcaだけ逆に測っている。なのでcが特別扱いされている感じがする
  • aが左に、bが右にあるとする ○ cがabの上にあるとき：μbacとμcbaは、(0,π)の間。μbcaは、(π, 2π)の間。なので、cは上に行き過ぎてはいけない ○ cがabの下にあるとき：μbcaは、(0,π)の間。μbacとμcbaは、(-π/2, 2π)の間。なので、cは下に行き過ぎてもいけない
  • というわけで、「ほとんど正」は、cが直線abから離れすぎない、という意味（どちらか側にある、という意味ではない

△abcがほとんど正だが正ではないときには、２つの角度が[0,-δ]の範囲にある、と言っている。ここから逆算すると、△abcが正、とは、cがabの上にある（cが、aからbを見た時に左側にある）という意味だと思われる。

と思ったけど、恐らく、論文でμbcaととなっているのはμacbの誤植。 μbac, μcba, μacbが[-δ, π+δ]の範囲にあるとき、△abcはほとんど正という、という定義だとして考えると・・同様に、aが左でbが右にある場合を考える。

  • cがabの上にあるとき、μbac, μcba, μacbのすべてが (0, π)の範囲（つまり、cはどこにでも動ける）
  • cがabの下にあるとき、μbac, μcbaは(-π/2, 0）でμacbが(π, 2π）の範囲（つまり、cはあまり下にはいけない） となって自然。△abcが正、とは、cがabの上にあるという定義は変わらずで良い。

T(a,b,c)

T(a,b,c) = △abcがほとんど正 T(a,b,c)は、△abcが正、という主張に対するα-predicateになる

TriagleTest(a,b,c) TriangleTest(a,b,c)は、T(a,b,c), T(a,c,b)に対するε-arithmeticになる。つまり、TT(a,b,c)は、cがabの左側にある、という関係を、小さな誤差を許容すれば判定できる