Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in $$O(k(n-k)\log ^2 n +n\log ^3 n)$$ O ( k ( n - k ) log 2 n + n log 3 n ) steps, where $$O(k(n-k))$$ O ( k ( n - k ) ) is the number of faces in the worst case. This result applies to disjoint line segments in the $$L_p$$ L p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, a running time with a polylog factor to the number of faces was only achieved for point sites in the $$L_1$$ L 1 or Euclidean metric before.