Download this article
 Download this article For screen
For printing
Recent Issues
Volume 19, Issue 1
Volume 18, Issue 1
Volume 17, Issue 1
Volume 16, Issue 2
Volume 16, Issue 1
Volume 15, Issue 2
Volume 15, Issue 1
Volume 14, Issue 2
Volume 14, Issue 1
Volume 13, Issue 2
Volume 13, Issue 1
Volume 12, Issue 1
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 1
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 1
Volume 5, Issue 2
Volume 5, Issue 1
Volume 4, Issue 1
Volume 3, Issue 1
Volume 2, Issue 1
Volume 1, Issue 1
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
 
Subscriptions
 
ISSN: 2157-5452 (e-only)
ISSN: 1559-3940 (print)
 
Author index
To appear
 
Other MSP journals
A connected component labeling algorithm for implicitly defined domains

Robert I. Saye

Vol. 18 (2023), No. 1, 29–54
Abstract

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
Mathematical Subject Classification
Primary: 65D99
Secondary: 14P10, 65D18
Milestones
Received: 29 May 2022
Accepted: 19 November 2022
Published: 15 June 2023
Authors
Robert I. Saye
Mathematics Group
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
United States