Naive方法，Rhynsburger（1973），是最早的方法之一，是对Voronoi图定义的直接转化。Bentley et al. （1980）结合bucketing技术，使算法的复杂度平均为O(n)。

另一种Naive方法，“walking method”。Voronoi图的顶点和边一个接一个的按顺序构造，好像沿Voronoi图的边行进一样。这种方法在1977年Lawson的关于Delaunay图文中有描述，Masus（1984）利用bucketing技术构造了平均复杂度为O(n)的算法。

“flip method”，最初先构造一个初始图，然后一步一步修改，直到它变为Voronoi图。它是Sibson在1978首先提出的。

Incremental 方法，是一个简单但是很有用的方法。先构造2个或3个generator的Voronoi图，然后再一个个地增加generator来修改Voronoi图。这种方法最早是Green 和Sibson（1978）提出的。以后很多人对这种方法进行了改进。这种方法在最坏的情况下时间复杂度是O(n2)，但是平均时间复杂度通过使用特殊的数据结构可以降到O(n)。这种方法无论是从时间复杂度还是鲁棒性地角度看，都是最实用的方法之一。

Divide-and-conquer 方法。Generator被递归的分为小子集，然后把这些子集的Voronoi图合并到一起。这种方法是Shamos 和Hoey（1975）最初提出的。最坏的情况下，这种方法的时间复杂度是O(nlogn)。同样的，以后也有很多人对这种方法做了进一步的工作，使其鲁棒性得到提高，平均时间复杂度也达到了O(n)。

Sweep line 方法。由Fortune（1986，1987）提出。Sweep line方法是计算几何最基本的技术之一，它把一个二维问题降为一维问题。一条垂直线，即sweep line，从平面的左面移到右面，Voronoi图就沿着这条线构造。

“lift-up method”，利用二维Voronoi图和三维凸包的关系构造Voronoi图。