A connected component labeling algorithm is developed for implicitly defined
domains specified by multivariate polynomials. The algorithm operates by recursively
subdividing the constraint domain into hyperrectangular subcells until the topology
thereon is sufficiently simple; in particular, we devise a topology test using
properties of Bernstein polynomials. In many cases the algorithm produces
a certificate guaranteeing its correctness, i.e., two points yield the same
label if and only if they are path-connected. To robustly handle various
kinds of edge cases, the algorithm may assign identical labels to distinct
components, but only when they are exactly or nearly touching, relative to
a user-controlled length scale. A variety of numerical experiments assess
the effectiveness of the overall approach, including statistical analyses on
randomly generated multicomponent geometry in 2D and 3D, as well as specific
examples involving cusps, self-intersections, junctions, and other kinds of
singularities.
Keywords
connected components, path connectedness, implicitly
defined domains, level set methods, Bernstein polynomials,
semialgebraic sets
