MunchLab / MunchLab/ceREEBerus
get_levelset_components is O(n²) via pairwise is_face checks in computereeb
@ishikaghosh2201 is already working on this.
Since Sep 17, 2026.
- Dominant language
- Jupyter Notebook
- Stars
- 5
- Forks
- 2
- PR merge metrics
- No merged PRs in 30d
Description
get_levelset_components(L) in cereeberus/compute/computereeb.py decides which simplices in the current sweep level-set belong to the same connected component by comparing every pair of simplices with is_face, which allocates two new set() objects per comparison:
for i, simplex1 in enumerate(L): for j, simplex2 in enumerate(L): if i < j: if is_face(simplex1, simplex2) or is_face(simplex2, simplex1): UF.union(i, j)
computeReeb calls this twice per sweep level, and the level-set can grow to hold a large fraction of the mesh's simplices, so this is a real cost driver for reasonably sized meshes. Confirmed directly against the current implementation: runtime roughly quadruples every time input size doubles (e.g. ~0.01s → ~11s from n=200 to n=6400).
Proposed fix
Since is_face(sigma, tau) just checks whether tau's vertex set is a subset of sigma's, each simplex's proper subsets (of every size, not just size 1 and 2) can be looked up directly in a dict keyed by tuple(sorted(subset)), instead of comparing every pair. A k-vertex simplex has 2^k - 2 nonempty proper subsets (6 for a triangle, 14 for a tetrahedron), so this is O(n·2^k) instead of O(n²) and stays cheap for any mesh with bounded simplex dimension
Profiled and proposed a fix here:
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.