@article{4095, abstract = {he kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E2 subdivides E2 into maximal regions such that all points within a given region have the same k nearest sites. Two versions of an algorithm are developed for constructing the kth-order Voronoi diagram of a set of n sites in O(n2 log n + k(n - k) log2 n) time, O(k(n - k)) storage, and in O(n2 + k(n - k) log2 n) time, O(n2) storage, respectively.}, author = {Chazelle, Bernard and Edelsbrunner, Herbert}, issn = {1557-9956}, journal = {IEEE Transactions on Computers}, number = {11}, pages = {1349 -- 1354}, publisher = {IEEE}, title = {{An improved algorithm for constructing kth-order Voronoi diagrams}}, doi = {10.1109/TC.1987.5009474}, volume = {36}, year = {1987}, }