在給定的圖形的情況下，那是不可能建立梯形地圖以線性時間

Question

[這對於在CS計算幾何]

比方說，我有一個V含vectices和e條邊的圖G，對於實例維羅諾圖VD（G）。

[I'd like to build a trapezodial map out of my given graph,][1] 

那是不可能建立的線性時間trapezodial地圖對於給定的圖形，相反的O（nlogn）經常性建設時間？

我一直在思考掃掠線梯形地圖的建設，在掃掠線的每個邊緣將構建上部和下部網站。

在先進的感謝

Answer 1

否，該圖可以由堆疊在彼此的頂部上V/2個水平區段。構建梯形圖表示按高度對這些段進行排序，並且至少需要c v log v時間。