2
$\begingroup$

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).

$\endgroup$

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.