K-set (geometry) - Construction Algorithms

Construction Algorithms

Edelsbrunner and Welzl (1986) first studied the problem of constructing all k-sets of an input point set, or dually of constructing the k-level of an arrangement. The k-level version of their algorithm can be viewed as a plane sweep algorithm that constructs the level in left-to-right order. Viewed in terms of k-sets of point sets, their algorithm maintains a dynamic convex hull for the points on each side of a separating line, repeatedly finds a bitangent of these two hulls, and moves each of the two points of tangency to the opposite hull. Chan (1999) surveys subsequent results on this problem, and shows that it can be solved in time proportional to Dey's O(nk1/3) bound on the complexity of the k-level.

Agarwal and Matoušek describe algorithms for efficiently constructing an approximate level; that is, a curve that passes between the (k - d)-level and the (k + d)-level for some small approximation parameter d. They show that such an approximation can be found, consisting of a number of line segments that depends only on n/d and not on n or k.