The ordered order-k Voronoi diagram (sometimes written OOKVD) partitions the plane into regions such that the k closest sites are the same and in the same order for all the points in a region.

I am interested in particular in the case k=n, the number of sites.

I would also like to know the upper and lower bounds in the worst-case of the number of faces.

I have found literature saying that these have been studied (e.g., http://ieeexplore.ieee.org/document/6222139/), but I failed to find those results in the references (mostly, they just define the OOKVD, and not discuss their combinatorial and algorithmic complexity).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.