Proximity in Arrangements of Algebraic Sets

Let X be an arrangement of n algebraic sets Xi in d-space, where the Xi 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 be used in the following proximity problems: given some point, find the k nearest sets Xi 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 Xi.