Before revision:  We formalize the concept  and prove that it is robust under an insertionoperation, thus ,  enabling its use in incremental constructions  .
After revision:  We formalize the concept and prove that it is robust under an insertionoperation, thus , enabling its use in incremental constructions . The time-complexity analysis of the resulting simple randomized incremental construction is non-standard, and interesting in its own right, because the intermediate Voronoi-like structures are order-dependent. We further extend the approach to compute the following structures in expected linear time: the order-(k+1) subdivision within an order-k Voronoi region, and the farthest abstract Voronoi diagram after the order of its regions at infinity is known .