MunchLab / MunchLab/ceREEBerus

get_levelset_components is O(n²) via pairwise is_face checks in computereeb

Open
#109 0 comments 0 reactions 1 assignee View on GitHub

@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:

levelset_components_On2.ipynb

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.