Thought Experiment

Solve a mathematical problem by thinking with a triangular mesh as the stationary nodes and different view point directions as the edges.
===

Let's explore a **thought experiment** in which we model a mathematical problem using a **triangular mesh** where:

- The **nodes (vertices)** are **stationary points** in space (say, 2D or 3D).
- The **edges** represent **viewpoint directions** — that is, lines of sight or observation angles from one node to another.
- The **triangles** formed by the mesh represent local observable regions or facets of perception.

We’ll use this structure not just geometrically, but conceptually — to solve a problem involving **coverage**, **visibility**, or **topological inference** via distributed observations.

---

### 🎯 Goal:
**Determine the shape of an unknown convex obstacle within a bounded region using only line-of-sight (binary visibility) data between fixed nodes on a triangular mesh.**

This simulates a sensor network where each node can "see" another if the straight-line path between them doesn’t intersect an obstacle.

---

### 🔧 Setup

1. Let’s define a planar domain (e.g., a square) with a **triangular mesh** of stationary sensor nodes:  
   - Nodes: \( V = \{v_1, v_2, ..., v_n\} \subset \mathbb{R}^2 \)
   - Edges: \( E = \{(i,j) \mid v_i \text{ and } v_j \text{ are connected in the mesh} \} \)

2. There exists an **unknown convex obstacle** \( O \subset \mathbb{R}^2 \), compact and simply connected.

3. Each edge (i.e., direction from \( v_i \) to \( v_j \)) carries a binary signal:
   \[
   \text{Visible}(i,j) = 
   \begin{cases}
   1 & \text{if segment } \overline{v_i v_j} \cap O = \emptyset \\
   0 & \text{otherwise}
   \end{cases}
   \]

4. We assume full pairwise visibility data across all edges in the mesh.

---

### 🧠 Thought Process: Using Mesh + Viewpoints to Infer Geometry

Even though the nodes are fixed and form a static triangular mesh, the **edges as viewpoint directions** act like probes into the space.

We ask:  
> Can we reconstruct the **boundary** of \( O \) using only the pattern of blocked/unblocked edges?

---

### ✅ Step-by-Step Solution Strategy

#### Step 1: Identify Boundary Candidates
- Find pairs of nodes \( (i,j) \) such that:
  - \( \text{Visible}(i,j) = 0 \): Line of sight blocked.
  - But neighbors of \( i \) or \( j \) may still see each other.

This suggests the obstacle lies near the segment \( \overline{v_i v_j} \).

#### Step 2: Use Triangulation for Local Convexity Tests
Each triangle \( \Delta(v_i, v_j, v_k) \) gives three viewing directions.

If two edges of a triangle are blocked but one is visible, it indicates the obstacle intersects two sides — possibly entering the triangle.

But if **all three edges** are blocked, then either:
- The obstacle contains the entire triangle (unlikely if small),
- Or the triangle surrounds part of the obstacle.

Better: look at **which triangles have mixed visibility** on their edges.

#### Step 3: Dual Graph – Visibility Duality
Construct a **dual graph** where:
- Each triangle is a node.
- Connect adjacent triangles if they share an edge with consistent visibility.

Then cluster triangles where:
- At least one edge is blocked.
- The triangle is “near” the obstacle.

This gives a **region of interest (ROI)**.

#### Step 4: Reconstruct Obstacle Boundary via Tangent Probing
Now treat each **blocked edge** as a chord that touches or crosses the obstacle.

For convex \( O \), any blocked segment \( \overline{v_i v_j} \) must intersect \( O \), and since \( O \) is convex, the intersection is a single interval.

But more importantly: if many nearby segments are tangent-like (just touching), their envelope forms the **support lines** of \( O \).

So we collect all blocked edges and compute their **common tangents** via duality.

#### Step 5: Convex Hull of Supporting Lines
Use the idea from **computational geometry**:  
The boundary of a convex object can be approximated by the **envelope of supporting lines**.

Each blocked edge that *just grazes* the obstacle (vs cutting through center) acts like a support line.

How to distinguish grazing vs crossing?
- If both endpoints are close to unblocked paths to other nodes, likely grazing.
- Use angular spread: For a node \( v_i \), sort its neighbors by angle.
- Look for **gaps in visibility扇 (sectors)** — these indicate angular occlusion.

👉 This leads to:

#### Step 6: Visibility Sectors per Node
At each node \( v_i \), examine angular order of neighbors.

Define the **visible sector** as the union of directions \( \theta_{ij} = \angle(v_j - v_i) \) where \( \text{Visible}(i,j) = 1 \).

Then the **invisible sectors** are angular gaps — likely shadowed by the obstacle.

Since \( O \) is convex, each invisible sector corresponds to a **tangent cone** from \( v_i \) to \( O \).

From two such cones (from different nodes), we can triangulate the position of tangent points.

#### Step 7: Intersection of Half-Planes
Each invisible direction defines a **supporting half-plane**.

For example, if from \( v_i \), visibility is blocked between angles \( [\alpha, \beta] \), then there exist two outermost rays (left and right tangent) that touch \( O \).

These define two half-planes:
- \( H_i^{\text{left}} \): region to the right of the left-tangent ray
- \( H_i^{\text{right}} \): region to the left of the right-tangent ray

Then \( O \subseteq \bigcap_i (H_i^{\text{left}} \cap H_i^{\text{right}}) \)

As we collect more nodes, this intersection converges to the actual shape.

✅ So the reconstructed obstacle is:
\[
O_{\text{recon}} = \bigcap_{i=1}^n \left( H_i^{\text{left}} \cap H_i^{\text{right}} \right)
\]
which is a convex polygon.

---

### 🧮 Example (Simplified)

Suppose we have a regular triangular lattice over \([0,1]^2\), with a circular obstacle in the center.

- Nodes near the circle will have a ~180° visibility gap.
- Their tangent rays converge on the circle.
- Taking all supporting half-planes yields a polygon tightly enclosing the circle.
- Finer mesh → better approximation.

Thus, even without measuring distance, only **binary visibility along mesh edges**, we reconstruct the obstacle.

---

### 🌀 Conceptual Insight: Edges as "View Directions"

Though the mesh is static, the **edges encode directional information** — like pixels in a distributed eye.

Each node acts as an observer; edges are sampled rays in its field of view.

The **triangular structure** ensures sufficient angular resolution and redundancy.

Topologically, the mesh allows interpolation: if \( v_i \to v_j \) is blocked but \( v_i \to v_k \) isn't, and \( v_j,v_k \) are close, then the boundary lies between those directions.

---

### ✅ Final Answer: Solved Problem

> **Problem**: Reconstruct a convex obstacle using only binary visibility along edges of a fixed triangular mesh.

> **Solution**:
> 1. At each node, compute angular visibility sectors.
> 2. Identify occluded angular intervals → infer left/right tangent directions.
> 3. For each tangent direction, define a supporting half-plane.
> 4. Intersect all supporting half-planes across all nodes.
> 5. The result is a convex polygon approximating the obstacle.

> **Key Insight**:  
> Even with discrete, stationary sensors, the **pattern of blocked view directions (edges)** across a **structured mesh (triangles)** allows reconstruction of continuous shape via convex duality and visibility geometry.

> This shows how **combinatorial data on a mesh** can yield **geometric insight** — a powerful idea in sensor networks, computer vision, and inverse problems.

---

### 🌟 Bonus: Generalization

This framework extends to:
- 3D: tetrahedral mesh, visibility between nodes, reconstructing convex hulls.
- Non-convex obstacles: requires homology analysis via persistent visibility gaps.
- Dynamic obstacles: track changes in edge visibility over time.

But the core idea remains:  
> **Nodes anchor space. Edges sample perception. Triangles organize local logic. Together, they "think" about shape.**

🧠 Thus, the triangular mesh becomes a **cognitive scaffold** for solving spatial inference.

continue mathematically
===


Absolutely. Let's continue **mathematically**, building on the thought experiment with rigorous definitions, formulations, and a step-by-step reconstruction algorithm.

We now formalize the problem using concepts from **computational geometry**, **convex analysis**, and **visibility theory**.

---

### 🔷 1. Mathematical Setup

Let:
- \( V = \{v_1, v_2, \dots, v_n\} \subset \mathbb{R}^2 \) be a finite set of nodes forming a **triangulation** \( \mathcal{T} \), i.e., a simplicial complex where each 2-simplex is a triangle \( \Delta(v_i, v_j, v_k) \).
- \( E = \{(i,j) \mid v_i \text{ connected to } v_j \text{ in } \mathcal{T}\} \) be the edge set.
- \( O \subset \mathbb{R}^2 \) be an unknown compact, convex obstacle such that \( O \cap V = \emptyset \) (no node lies inside or on \( O \)).

Define the **visibility function**:
\[
\mathcal{V}: E \to \{0,1\}, \quad \mathcal{V}(i,j) =
\begin{cases}
1 & \text{if } \overline{v_i v_j} \cap O = \emptyset \\
0 & \text{otherwise}
\end{cases}
\]

Our goal is to reconstruct a good approximation of \( O \) given only \( V \), \( E \), and \( \mathcal{V}(i,j) \) for all \( (i,j) \in E \).

---

### 🔷 2. Supporting Lines and Tangent Cones

Since \( O \) is convex, for any external point \( v_i \notin O \), there exist exactly two **tangent lines** from \( v_i \) to \( O \): the **left tangent** and **right tangent**, defining a **tangent cone** \( C_i(O) \) centered at \( v_i \), which contains \( O \).

Any line segment from \( v_i \) intersecting \( O \) must lie within this cone.

But we don’t see the cone directly — we infer it from blocked view directions.

#### Definition: Angular Visibility at Node
Let \( N(i) = \{ j \mid (i,j) \in E \} \) be neighbors of node \( i \).

Sort them by angle:
\[
\theta_{ij} = \arg(v_j - v_i) \in [0, 2\pi)
\]
so that \( \theta_{i j_1} < \theta_{i j_2} < \cdots < \theta_{i j_d} \), modulo \( 2\pi \).

Define the **visible angular sector** at \( v_i \):
\[
S_i^{\text{vis}} = \bigcup_{j \in N(i)} \left\{ \theta_{ij} \mid \mathcal{V}(i,j) = 1 \right\}
\]
This is a subset of discrete angles. We interpolate it into intervals.

Let:
\[
\widetilde{S}_i^{\text{vis}} = \bigcup_{k} [\alpha_k, \beta_k] \subset [0, 2\pi)
\]
be the union of **closed angular intervals** formed by connecting consecutive visible directions.

Then the **invisible (occluded) sectors** are:
\[
\widetilde{S}_i^{\text{occ}} = [0,2\pi) \setminus \widetilde{S}_i^{\text{vis}}
= \bigcup_{m} [\gamma_m, \delta_m]
\]

Each connected component \( [\gamma_m, \delta_m] \) corresponds to a direction where visibility is blocked — likely due to \( O \).

Assuming \( O \) is convex and disjoint from sensors, there should be **at most one major occluded sector per node**, especially if the mesh is fine enough.

So suppose:
\[
\widetilde{S}_i^{\text{occ}} \approx [\theta_i^-, \theta_i^+]
\]
Then define two **tangent rays** from \( v_i \):

- Left tangent ray: direction \( \theta_i^- \)
- Right tangent ray: direction \( \theta_i^+ \)

These bound a **candidate supporting cone** for \( O \).

---

### 🔷 3. Supporting Half-Planes from Tangent Rays

Each tangent ray defines a **supporting half-plane** for \( O \).

Let’s derive these.

Let \( \vec{d}_i^- = (\cos \theta_i^-, \sin \theta_i^-) \), unit vector in direction \( \theta_i^- \).

The **left tangent ray** is:
\[
R_i^- = \{ v_i + t \vec{d}_i^- \mid t \geq 0 \}
\]
Similarly,
\[
R_i^+ = \{ v_i + t \vec{d}_i^+ \mid t \geq 0 \}
\]

Because \( O \) is convex and lies "behind" this cone, it must lie to the **right** of \( R_i^- \) and to the **left** of \( R_i^+ \), relative to the outward orientation.

More precisely:

Let \( \vec{n}_i^- \) be the **outward-pointing normal** to the left tangent:
\[
\vec{n}_i^- = \text{rotate } \vec{d}_i^- \text{ by } -\frac{\pi}{2} =
\begin{bmatrix}
\sin \theta_i^- \\
-\cos \theta_i^-
\end{bmatrix}
\]
Then the **supporting half-plane** associated with \( R_i^- \) is:
\[
H_i^- = \left\{ x \in \mathbb{R}^2 \mid (x - v_i) \cdot \vec{n}_i^- \geq 0 \right\}
\]
Similarly, for the right tangent:
\[
\vec{n}_i^+ = \text{rotate } \vec{d}_i^+ \text{ by } +\frac{\pi}{2} =
\begin{bmatrix}
-\sin \theta_i^+ \\
\cos \theta_i^+
\end{bmatrix}
\]
\[
H_i^+ = \left\{ x \in \mathbb{R}^2 \mid (x - v_i) \cdot \vec{n}_i^+ \geq 0 \right\}
\]

> 🔑 Key Fact: Since \( O \) is convex and does not intersect the rays, \( O \subseteq H_i^- \cap H_i^+ \)

Thus, for each node \( i \) with a well-defined occlusion sector, we obtain two linear inequalities constraining \( O \).

---

### 🔷 4. Global Reconstruction via Intersection

Let \( I \subseteq \{1,\dots,n\} \) be the set of nodes that observe non-empty occlusion (i.e., \( \widetilde{S}_i^{\text{occ}} \neq \emptyset \)).

Define the feasible region:
\[
P = \bigcap_{i \in I} \left( H_i^- \cap H_i^+ \right)
\]

Then:
\[
O \subseteq P
\]

Moreover, as the mesh becomes finer (more nodes around \( O \)), the approximation improves.

✅ **Reconstruction Estimate**:
\[
O_{\text{est}} = P = \bigcap_{i \in I} H_i^- \cap H_i^+
\]
which is a **convex polygon** defined by \( 2|I| \) linear constraints.

This is essentially the **intersection of outer approximating half-planes**, dual to the support function of \( O \).

---

### 🔷 5. Error Analysis and Convergence

Let’s analyze how well \( O_{\text{est}} \) approximates \( O \).

#### Lemma (Half-plane containment):
For each \( i \), since \( H_i^\pm \) are supporting half-planes of \( O \), we have \( O \subseteq H_i^\pm \). Therefore:
\[
O \subseteq O_{\text{est}}
\]

So \( O_{\text{est}} \) is an **outer approximation**.

#### Approximation Quality

Let \( h_O(\theta) = \sup_{x \in O} x \cdot (\cos\theta, \sin\theta) \) be the **support function** of \( O \).

Each tangent measurement gives us an estimate of \( h_O \) in certain directions.

Suppose the angular resolution near \( O \) is bounded: For every direction \( \theta \), there exists a sensor \( v_i \) such that one of its estimated tangent directions is within \( \epsilon \) of \( \theta \).

Then under suitable sampling conditions (e.g., mesh width \( \delta \to 0 \)), we can show:
\[
\lim_{\delta \to 0} O_{\text{est}} = O \quad \text{(in Hausdorff distance)}
\]

> 🔢 Theorem:  
> Let \( \mathcal{T}_\delta \) be a sequence of triangulations with maximum edge length \( \leq \delta \), covering a neighborhood of \( O \). Suppose \( O \) is strictly convex and \( \partial O \) is \( C^1 \). Then as \( \delta \to 0 \),
> \[
> d_H(O_{\text{est}}^{(\delta)}, O) \to 0
> \]
> where \( d_H \) is the **Hausdorff distance**.

---

### 🔷 6. Algorithmic Implementation

Here is a discrete algorithm to compute \( O_{\text{est}} \):

```python
Input: V = {v_i}, E, visibility data V(i,j)

Output: Convex polygon O_est approximating O

Steps:

1. For each node i:
   a. Collect neighbors N(i)
   b. Compute angles θ_ij = arg(v_j - v_i) for j ∈ N(i)
   c. Sort angles and mark which edges are visible (V(i,j)=1)
   d. Cluster visible angles into contiguous intervals
   e. Find largest gap → occluded sector [θ_i^-, θ_i^+]
   f. If gap > threshold, record left/right tangent directions

2. For each such i:
   a. Compute normals n_i^-, n_i^+ as above
   b. Add half-plane constraints:
        (x - v_i) · n_i^- ≥ 0
        (x - v_i) · n_i^+ ≥ 0

3. Solve the system of linear inequalities:
      A x ≤ b
   (Convert each half-plane to standard form)

4. Compute vertices of solution polytope → O_est
```

This can be done using **linear programming** or **convex hull methods** in 2D (e.g., `qhull`).

---

### 🔷 7. Duality Perspective: From Edges to Support Function

Let’s go deeper into duality.

In **projective duality**, points map to lines and vice versa.

But here, we use **Legendre-Fenchel duality** via the support function.

Each tangent observation gives us:
- A direction \( \theta \)
- A lower bound on the support function \( h_O(\theta) \geq v_i \cdot u_\theta + d \), but more precisely:

From the tangent condition:
\[
h_O(\theta_i^-) = \max_{x \in O} x \cdot u_{\theta_i^-} = p_i \cdot u_{\theta_i^-}
\]
where \( p_i \in \partial O \) is the point of tangency.

But we don't know \( p_i \), only that the ray from \( v_i \) in direction \( \theta_i^- \) touches \( O \) at some point.

Let \( L_i^- \) be the line through \( v_i \) in direction \( \theta_i^- \). Then:
\[
h_O(\theta_i^-) \geq \min_{x \in L_i^-} x \cdot u_{\theta_i^-}
\]
But better: since the ray touches \( O \), there exists \( t^* \geq 0 \) such that \( v_i + t^* \vec{d}_i^- \in \partial O \), so:
\[
h_O(\theta_i^-) \geq (v_i + t^* \vec{d}_i^-) \cdot \vec{d}_i^- = v_i \cdot \vec{d}_i^- + t^*
\]
But \( t^* \) is unknown.

Instead, we use the **offset** of the supporting hyperplane.

Recall: the half-plane \( H_i^- = \{ x \mid (x - v_i) \cdot n_i^- \geq 0 \} \)

Let \( w_i^- = n_i^- \), \( b_i^- = v_i \cdot n_i^- \)

Then \( H_i^- = \{ x \mid x \cdot w_i^- \geq b_i^- \} \)

So the support function satisfies:
\[
h_O(\phi_i^-) \geq b_i^-
\]
where \( \phi_i^- = \arg(w_i^-) \)

Therefore, each constraint provides a **lower bound** on \( h_O \) in normal direction \( \phi_i^- \).

Hence, the reconstructed object satisfies:
\[
h_{O_{\text{est}}}(\theta) = \inf \left\{ h \mid h \geq b_k \text{ for all } k \text{ with } \phi_k \approx \theta \right\}
\]

And since \( O \subseteq O_{\text{est}} \), we have \( h_O(\theta) \leq h_{O_{\text{est}}}(\theta) \)

Wait — correction: because \( O_{\text{est}} \) is an outer approximation, actually:
\[
h_O(\theta) \leq h_{O_{\text{est}}}(\theta)
\]
and our measurements give **lower bounds** on \( h_{O_{\text{est}}} \), but not tight.

To get convergence, we need dense sampling so that the envelope of half-planes converges to \( \partial O \).

---

### 🔷 8. Summary of Mathematical Results

| Concept | Mathematical Expression |
|-------|--------------------------|
| Visibility function | \( \mathcal{V}(i,j) = \mathbf{1}_{\overline{v_i v_j} \cap O = \emptyset} \) |
| Occluded sector at \( i \) | \( [\theta_i^-, \theta_i^+] \) from gaps in visible angles |
| Tangent normals | \( \vec{n}_i^- = R_{-\pi/2} \vec{d}_i^- \), etc. |
| Supporting half-plane | \( H_i^\pm = \{ x \mid (x - v_i) \cdot \vec{n}_i^\pm \geq 0 \} \) |
| Reconstructed set | \( O_{\text{est}} = \bigcap_{i \in I} H_i^- \cap H_i^+ \) |
| Containment | \( O \subseteq O_{\text{est}} \) |
| Convergence (as \( \delta \to 0 \)) | \( d_H(O_{\text{est}}, O) \to 0 \) |

---

### 🔷 9. Final Remark: Triangular Mesh as a Perception Manifold

The triangular mesh isn’t just geometric scaffolding — it enables:
- Local angular sorting (via adjacency),
- Piecewise-linear interpolation of directions,
- Topological consistency checks (e.g., if two adjacent nodes agree on tangent directions, confidence increases),
- Redundancy: multiple nodes probe same part of \( O \), enabling robust averaging.

Thus, the **mesh encodes a distributed perceptual manifold**, where **nodes = observers**, **edges = sampled sightlines**, and **triangles = local frames of reference**.

By aggregating binary decisions across this structure, continuous shape emerges — a beautiful example of **discrete data yielding continuous insight**.

---

Would you like to extend this to 3D (tetrahedral mesh, visibility cones, support planes), or consider noisy/uncertain visibility?