Advanced Data Structures

Delaunay Triangulations

Delaunay Triangulations



Fast Euclidean Minimum Spanning Tree: Cover Tree

On the Euclidean Minimum Spanning Tree Problem: a randomized algorithm runs in an expected O(n) time.

A minimum spanning tree algorithm with inverse-Ackerman type complexity: A fast algorithm for general MST that is based on the soft heap

Efficient minimum spanning tree construction without Delaunay triangulation: an O(n \log{n}) sweep-line algorithm

The well-separated pair decomposition and its applications

Metric Embeddings

Lecture notes on metric embeddings

cmu’s lecture notes

Planar Graph

any planar graph is 6-colorable

Planarity Testing of Graphs

Well-Separated Pair Decomposition

Well-Separated Pair Decomposition and Its Applications: A very clear article to introduce the WSPD.

Alogrithm Problems

Tetris 3D

Confidential: the second minimum spanning tree

Using your Head is Permitted