2025-10-10

The problem seems to be more difficult than I originally thought, so I’ve decided to start by working in 3D and hope the method translates well to 4D.

Problem Statement: Given a 2-complex $\mathcal{M}\subset [0,1{]}^3$, find a 2-chain in the tetrahedralization of the unit cube $[0,1{]}^3$ that approximates $\mathcal{M}$.

We could try to solve this with an MIP, but I’m not entirely sure on the right objective function. Instead we use a heuristic as we also want to introduce noise anyways.

Idea of a heuristic:

1. For each triangle $t\in \mathcal{M}$:
   1. Compute centroid $p$ for triangle $t$
   2. For each tetrahedron $\sigma \in \mathcal{C}$
      1. Calculate the barycentric coordinates $[{\lambda }_1,\dots ,{\lambda }_4]$ of $p$ with respect to $\sigma$
      2. For $i=1,\dots ,4$, if $|{\lambda }_i|<ϵ$, mark the triangle corresponding to $i$.
2. Take the union of all marked triangles
3. Fill holes

It creates the general shape, but there a ton of holes many of which are too large to fill. The problem may be that I’m only sampling one point of the triangle. One modification is sample several points:

1. For each triangle $t\in \mathcal{M}$:
   1. Construct a set of samples points $P$ lying in $t$
   2. For each point $p\in P$ and tetrahedron $\sigma \in \mathcal{C}$
      1. Calculate the barycentric coordinates $[{\lambda }_1,\dots ,{\lambda }_4]$ of $p$ with respect to $\sigma$
      2. For $i=1,\dots ,4$, if $|{\lambda }_i|<ϵ$, mark the triangle corresponding to $i$.
2. Take the union of all marked triangles
3. Fill holes

Running this code (without hole filling) gives the following result (after 10 minutes):

Which is rife with holes but is approximately sphere shaped. Maybe with perfect settings this approach would work?

Alternative approach would be some sort of MIP:

$$\begin{array}{rlr}& \min & \sum c_i{x}_i\\ & \text{s.t.}& \Vert t-x_i\Vert \le ϵ\\ & & x_i\in \{0,1\}\end{array}$$

where $t$ is the current target triangle and $x_i\in \{0,1\}$ is selecting specific triangles which have volume $c_i$. My concern with this approach is that is very localized, i.e., there is no guarantee that the connection between triangles are shared. Capturing that may require constructing a dual graph:

$G=(V,E)$ where

• $v\in V$ corresponds to a triangle $t\in \mathcal{C}$
• $\{u,v\}\in E$ corresponds to two triangle $t_1,t_2\in \mathcal{C}$ that share an edge

Then we could capture the connection similar to TSP?