K-transversals of parallel convex sets
Nina Amenta · Canadian Conference on Computational Geometry · 1996
R d can be divided into a union of parallel (d\\Gammak)-flats of the form x 1 = g 1 ; x 2 = g 2 ; : : : x k = g k , where the g i are constant. Let C be a family of parallel (d \\Gamma k)-dimensional convex sets, meaning that each is contained in one of the above parallel (d \\Gamma k)-flats. We give a parameterization of the set of k-flats in R d , such that the set of k-flats which intersect, in a point, any set c 2 C, is convex. Parameterizing the lines in R 3 through horizontal convex sets as convex sets has applications to medical imaging, and interesting connections with recent work on light field rendering in computer graphics. The general case is useful for fitting k-flats to points in R d . The following easy reduction is well known. Let C be a finite set of parallel line segments in R d . We want to find a (d \\Gamma 1)-transversal for C, that is, a hyperplane intersecting every segment in C. Such a hyperplane has to pass below the upper endpoint of each segment and ...