How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Generic lower lifted facets project to a triangulation of the convex hull
Statement
Let and let be a finite indexed weighted site set of affine dimension in . Lift each site to height in the fixed ordered formal field of Stable-id lexicographic lift perturbation for cocircular and power ties. A lower simplex is the projection of affinely independent lifted sites whose graph hyperplane has every lifted site on or above it. Then the lower simplices cover and intersect in common faces. Each lower simplex has a weakly empty power sphere for the original unperturbed weighted sites.
Facts & Assumptions
Given: A finite indexed site universe, a finite nonempty site subset of projected affine dimension , and the common formal height perturbation fixed before all predicates.
Finite indexed geometric site sets and duplicate handling: is finite, its sites have distinct stable integer identifiers, and coordinates and weights are dyadic, with absent weights equal to zero.
Stable-id lexicographic lift perturbation for cocircular and power ties: every site height is perturbed by the same fixed-universe monomial, and the order of a nonzero polynomial is the sign of its least-exponent nonzero coefficient.
The finite lexicographic lift tie-break is coherent: a determinant on affinely independent projected sites and one distinct query site has a nonzero formal polynomial, and nonzero constant terms keep their signs.
The lifted determinant records a power-sphere side: the unperturbed lifted determinant equals minus the base orientation determinant times the query's power-distance difference from the base power sphere.
The projected sites affinely span .
Proof
Fix . A feasible representation is a vector with , , and . Its formal height is . If its support has more than sites, the vectors are linearly dependent, so there is a nonzero vector on that support with and . Such a vector has both positive and negative entries. Choose one of the two directions that does not increase and increase until a coefficient first becomes zero. This preserves feasibility and reduces support. Repeating finitely gives a feasible representation of support at most with no greater height.
There are finitely many supports of size at most . For any affinely independent support, its coefficients representing are unique; any dependent support reduces by step 1.1. Therefore the minimum formal height among feasible representations is attained among a finite nonempty set of basic supports.
Exclude temporarily the finite union of convex hulls of subsets of at most sites. For an outside this union, choose a minimizing support of smallest cardinality; it has exactly sites, is affinely independent, and has strictly positive coefficients . Indeed, a dependent support reduces by step 1.1 without increasing its minimal height, contradicting minimal cardinality. For any other site , write its unique affine coordinates , . For sufficiently small positive , replacing by and adding coefficient at remains feasible. Minimality gives . Hence the hyperplane through the lifted support sites lies below every lifted site and its projected simplex contains .
The set excluded in step 3.1 lies in a finite union of proper affine subspaces. A line segment in any open ball of can be chosen in a direction not parallel to any of these subspaces; each subspace then removes at most one point of the segment. Thus the complement is dense in the interior. The interior is dense in the whole convex hull: join any hull point to a fixed interior point, and every point of the joining segment other than the hull endpoint is interior by convexity. There are finitely many -tuples of sites, hence finitely many lower simplices; their projected simplices are closed. Step 3.1 puts a dense subset of in their union, so that finite union covers the entire convex hull.
If a lower hyperplane contained at least lifted sites, its projected face would contain a nondegenerate -tuple and an additional site, contradicting the nonzero determinant from [F3]. Thus every full-dimensional lower cell is a simplex. If two projected lower simplices have support planes , all their vertices lie on or above both supporting planes. For a point in the intersection of their projections, the two lifted convex combinations at therefore force and ; hence . On each simplex the corresponding plane difference has one sign at every vertex, so its zero set is a face. If , the nonzero determinant [F3] forces the same vertices. Thus intersections are common faces.
The supporting inequality for a formal lift has nonnegative constant-term difference at each site; otherwise its negative constant coefficient would force a negative formal sign by [F3]. The constant terms therefore give the unperturbed weak support inequalities, and [F4] identifies them with empty power spheres.
Depends on
Used by
Dependency tree · two levels
5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Chapter 9 (standard reference, not scraped)
- CGAL 6.3 User Manual, 3D Triangulations, The Delaunay and Regular Triangulations (standard reference, not scraped)