Proximity in Arrangements of Algebraic Sets
J. H. Rieger · SIAM Journal on Computing · 1999
Let X be an arrangement of n algebraic sets X i in d-space, where the X i are either parametrized or zero-sets of dimension $0\le m_i\le d-1$. We study a number of decompositions of d-space into connected regions in which the distance-squared function to X has certain invariances. Each region is contained in a single connected component of the complement of the bifurcation set $\cB$ of the family of distance-squared functions or of certain subsets of $\cB$. The decompositions can beused in the following proximity problems: given some point, find the k nearest sets X i in the arrangement, find the nearest point in X, or (assuming that X is compact) find the farthest point in X and hence the smallest enclosing $(d-1)$-sphere. We give bounds on the complexity of the decompositions in terms of n, d, and the degrees and dimensions of the algebraic sets X i .