凸多邊形相似判定問題

唐樂紅

(福州陽光學院， 福建福州 350015)

凸多邊形相似判定問題

唐樂紅

(福州陽光學院， 福建福州 350015)

本文通過利用已有的秘密判定相等協議、 集合相等判定協議、 數據對應成比例判定協議， 設計出凸多邊形相似判定協議， 并分析了其正確性、 安全性和復雜性.

計算幾何； 集合相等； 凸多邊形； 相似判定

0 引言

如果一個多邊形的所有邊中， 任意一條邊向兩方無限延長成為一條直線時， 其他各邊都在這條直線的同一側， 那么我們就稱這個多邊形為凸多邊形(邊數大于3). 生活中常見的正多邊形等都是凸多邊形. 判定兩個凸多邊形是否相似， 在數學、 物理等學科上都有很多的實際應用.

本文假定雙方的計算環境是安全的， 且前提 是雙方都能嚴格遵守協議的規程. 在滿足以上條件的情況下， 利用秘密判定相等協議、 集合相等判定協議、 數據對應成比例判定協議， 本文設計出凸多邊形相似判定協議.

1 基礎協議

1.1 秘密判定相等協議

兩個用戶希望在不向對方泄露自己數據信息的情況下， 比較出各自所持有數據是否相等. 如果雙方數據不相等時， 則要求任何一方都不能夠知道對方的數據. 這就是秘密判定問題[1].

1.2 集合相等判定協議

兩個用戶各自擁有一個集合， 如何在不泄露雙方各自集合信息的情況下， 判定出兩個集合是否相等[2]， 這就是集合相等判定問題. 協議具體如下：

輸入： Alice擁有集合X={x1,…,xm},Bob擁有集合Y={y1,…,ym}.

輸出： 謂詞P(X,Y).

執行過程：

(3) Alice和Bob各自在本地利用商量好的散列函數， 計算出S′=hash(S)和T′=hash(T).