\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2018年12月23日 星期日

[ lower convex hull self-balancing binary search tree ] 下凸包平衡樹

下凸包平衡樹是一個動態維護下凸包的資料結構,他至少能在$\ord{\log n}$時間完成以下兩個操作:
  1. 查詢 point(x,y) 是否被包含於下凸包中
  2. 將 point(x,y) 加入至下凸包中,然後將不位於下凸包頂點上的點刪除
由於繼承自C++ STL map,因此所有能對map用的操作都能被使用,對於那些會改動map資料的操作請小心使用避免影響到凸包的正確性,例如operator[]就盡量不要使用。

對於某些動態規劃問題需要用凸包斜率優化時應該非常有用,有空會補上專門用來動態做斜率優化的版本

沒有留言:

張貼留言