設 A 和 B 是平面上的兩組點,每組由 n 個點組成。我正在嘗試找到一種有效的方法來確定 A 和 B 是否可以被磁盤分隔 - 是否存在磁盤 D 使得 A 的所有點都位于 D 內,而 B 的所有點都位于 D 之外?
還有一個提示:使用提升到三個維度。
任何幫助將不勝感激。
uj5u.com熱心網友回復:
將點嵌入為 (x, y) ? (x, y, x2 y2) 并測驗是否存在分離超平面。這有效,因為
如果我們有引數 (a, b, c) 使得 ax by x2 y2 < c 如果 (x, y) ∈ A 并且 > c 如果 (x, y) ∈ B,那么比較等價于 (x ? (?a/2))2 (y ? (?b/2))2 ? c (?a/2)2 (?b/2)2,相當于一個圓心為 (?a/2, ?b/2) 半徑為 √(c (?a/2) 的分隔圓2 (?b/2)2);
相反,我們可以做代數從分離圓到分離超平面。
轉載請註明出處,本文鏈接:https://www.uj5u.com/qukuanlian/422809.html
標籤:
下一篇:找到最大重復子樹
