Simultaneous polygonalization of finite embedded plane graphs #
This file formalizes the separation part of Moise Chapter 6, Theorem 2. The first construction chooses the disjoint circular regions around graph vertices from Moise's Figure 6.1. Later constructions trim each embedded edge at the last exits from those regions and polygonalize the remaining pairwise-disjoint compact arcs.
The last parameter at which an arc lies in a closed disk.
Instances For
A last exit which may occur at the initial endpoint when the arc starts on the sphere.
Instances For
Ordered exits of an arc from two disjoint endpoint disks.
Instances For
Ordered exits for an arc whose endpoints already lie on the two boundary circles.
Instances For
The only point of a radial segment on its outer circle is its endpoint.
Concatenating two simple paths whose ranges meet only at their common endpoint is simple.
Moise's pairwise-disjoint circular vertex regions, also disjoint from every nonincident embedded edge.
- radius : ℝ
The
radiusdeclaration. - vertices_disjoint (v w : K.Vertex) : v ≠ w → Disjoint (Metric.closedBall (h (K.position v)) self.radius) (Metric.closedBall (h (K.position w)) self.radius)
- avoids_nonincident_edge (v : K.Vertex) (e : K.EdgeFace) : v ∉ ↑e → Disjoint (Metric.closedBall (h (K.position v)) self.radius) (Metric.cthickening self.radius (h '' K.cellCarrier ↑e))
Instances For
The edgeCurve declaration.
Equations
- K.edgeCurve h i t = h ((AffineMap.lineMap (K.position (K.edgeFirst i)) (K.position (K.edgeSecond i))) t)
Instances For
The two ordered circle crossings which delimit the central part of an embedded edge.
Instances For
The vertex-disk choice in Moise 6.2, Figure 6.1.
All separation properties survive shrinking the common vertex radius.
Equations
- LeanEval.Topology.ClassificationOfSurfaces.Moise.PlaneComplex.VertexDiskControl.shrink K D r hr hrD = { radius := r, radius_pos := hr, vertices_disjoint := ⋯, avoids_nonincident_edge := ⋯ }
Instances For
The centralCarrier declaration.
Instances For
The edgeTrim declaration.
Equations
- K.edgeTrim hcont D i = Classical.choice ⋯
Instances For
Pairwise-disjoint closed tubes around all trimmed central arcs.
- radius : ℝ
The
radiusdeclaration. - pairwise_disjoint (i j : Fin (Fintype.card K.EdgeFace)) : i ≠ j → Disjoint (Metric.cthickening self.radius (K.edgeTrim hcont D i).centralCarrier) (Metric.cthickening self.radius (K.edgeTrim hcont D j).centralCarrier)
Instances For
A polygonal replacement for one trimmed central arc, kept inside its assigned tube.
- data : BrokenLineData (Metric.thickening C.radius (K.edgeTrim hcont D i).centralCarrier ∩ (convexHull ℝ) (h '' K.cellCarrier ↑(K.edgeAt i)))
The
datadeclaration.
Instances For
The centralPolygonalArc declaration.
Equations
- K.centralPolygonalArc hcont D C i = Classical.choice ⋯
Instances For
The loop-resolved middle remains in the convex hull of the original target edge.
A simple parameterization of the polygonal replacement, normalized to the unit interval.
- source : PlaneComplex
The
sourcedeclaration. The
mapdeclaration.The
curvedeclaration.- source_support : self.source.support = segment ℝ (planePoint 0 0) (planePoint (↑A.data.resolvedWalk.length) 0)
- map_affineOn (s : Finset self.source.Vertex) : s ∈ self.source.simplexes → IsAffineOn self.map (self.source.cellCarrier s)
- continuousOn : ContinuousOn self.curve (Set.Icc 0 1)
Instances For
The polygonal arc model from Chapter 6.1 gives a continuous injective unit-interval parameterization.
The parameterization declaration.
Equations
Instances For
The portion of the polygonal replacement between its ordered exits from the endpoint disks.
Equations
Instances For
The trimmedCarrier declaration.
Equations
Instances For
The leftEndpoint declaration.
Equations
Instances For
The rightEndpoint declaration.
Equations
Instances For
The leftSpoke declaration.
Instances For
The rightSpoke declaration.
Equations
- A.rightSpoke = segment ℝ A.rightEndpoint (h (K.position (K.edgeSecond i)))
Instances For
The complete polygonal replacement of an edge: a radial spoke, the trimmed middle arc, and a second radial spoke.
Equations
- A.completeCarrier = A.leftSpoke ∪ A.trimmedCarrier ∪ A.rightSpoke
Instances For
Every complete finite replacement edge stays in the convex hull of its original target edge. In particular, simultaneous finite graph approximation preserves any convex target such as the model half-plane.
The leftOpenSpoke declaration.
Instances For
The rightOpenSpoke declaration.
Equations
- A.rightOpenSpoke = A.rightSpoke \ {h (K.position (K.edgeSecond i))}
Instances For
The relative interior of a replacement edge.
Equations
Instances For
The trimmed middle arc as a path.
Equations
- A.middlePath = { toFun := fun (t : ↑unitInterval) => A.parameterization.curve ((Path.segment A.exitData.left A.exitData.right) t), continuous_toFun := ⋯, source' := ⋯, target' := ⋯ }
Instances For
The full replacement path for an edge.
Equations
- A.completePath = (Path.segment (h (K.position (K.edgeFirst i))) A.leftEndpoint).trans (A.middlePath.trans (Path.segment A.rightEndpoint (h (K.position (K.edgeSecond i)))))
Instances For
Every complete replacement edge is a simple path.
Distinct replacement edges have disjoint relative interiors.
The selected replacement arc for an enumerated edge.
Equations
- K.replacementArc hcont D C i = K.centralPolygonalArc hcont D C i
Instances For
The rawMiddleBreakpoint declaration.
Equations
Instances For
The middleSourceScalarMap declaration.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The middleSourceMap declaration.
Equations
Instances For
The middleBreakpoint declaration.
Equations
- K.middleBreakpoint A v = max (1 / 2) (min (3 / 4) (K.rawMiddleBreakpoint A v))
Instances For
The finite set of all source breakpoints: the two spoke joins and every vertex of every middle PL model.
Equations
- K.GraphBreakpoint hcont D C = ((i : Fin (Fintype.card K.EdgeFace)) × Option (Option (K.replacementArc hcont D C i).parameterization.source.Vertex))
Instances For
The graphBreakpointParameter declaration.
Equations
- K.graphBreakpointParameter hcont D C b = match b.snd with | none => 1 / 2 | some none => 3 / 4 | some (some v) => K.middleBreakpoint (K.replacementArc hcont D C b.fst) v
Instances For
The graphBreakpointPoint declaration.
Equations
- K.graphBreakpointPoint hcont D C b = (AffineMap.lineMap (K.position (K.edgeFirst b.fst)) (K.position (K.edgeSecond b.fst))) (K.graphBreakpointParameter hcont D C b)
Instances For
The common source subdivision carrying all edgewise PL breakpoints.
Equations
- K.graphReplacementSubdivision hcont D C = K.markedEdgeSubdivision (K.graphBreakpointPoint hcont D C)
Instances For
The replacement map on the affine line carrying one source edge.
Equations
- K.edgeReplacementMap hcont D C i x = (K.replacementArc hcont D C i).completePath.extend ((K.edgeParameter i) x)
Instances For
The IsGraphVertexPoint declaration.
Instances For
The edgeIndexAt declaration.
Equations
- K.edgeIndexAt x hx = Classical.choose hx
Instances For
The simultaneous replacement map. Active graph vertices are handled first; every other point of the graph lies in the open part of a unique edge.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The finite simultaneous graph replacement remains in the convex hull of the original target graph.
The simultaneous edge replacement is affine on every face of its named common source subdivision.
The simultaneous edge replacement is PL on the original graph. All breakpoints of all polygonal middle arcs occur as vertices of one common finite subdivision.
Moise's simultaneous polygonal replacement gives a PL embedding of the finite source graph, before imposing a quantitative approximation bound.
If the image of every source face has diameter below η, and both geometric controls are
smaller than η, then simultaneous polygonal replacement moves every graph point by less than
2 * η.
Moise Chapter 6, Theorem 2 for finite plane complexes: after first sampling the source graph finely, simultaneous polygonal replacement gives an arbitrarily close PL embedding and preserves every original vertex value.
Moise Chapter 6, Theorem 2 in its conventional interface.