Source-linked AI summary
The Discrete Harmonic Center of a Quadrilateral
Marc Alexa
TL;DR
The paper asks how to choose an inserted point for a quadrilateral fan so that the piecewise linear interpolant has minimal Dirichlet energy. It uses fan triangulation, cotangent-energy analysis, and spoke-current closure conditions to characterize the optimum. The minimizing location is a unique, data-independent discrete harmonic center that is Möbius-covariant, has closed forms for tangential and cyclic quadrilaterals, and generalizes in data-independence to d + 2-vertex polytopes.
Problem
The paper studies how to minimize Dirichlet energy over the location of an inserted vertex in a quadrilateral fan, extending energy minimization beyond choosing a triangulation diagonal.
Method
The authors analyze the fan's cotangent Dirichlet energy and characterize optimality using spoke currents, cyclic closure conditions, and the Möbius involution exchanging opposite corners.
Results
The minimizing location is a unique discrete harmonic center independent of corner values and Möbius-covariant; it has closed forms for tangential and cyclic quadrilaterals.
Takeaways & Limitations
The center is distinct from affine quadrilateral centers and remains data-independent for polytopes with d + 2 vertices in dimension d.
Takeaways & Limitations
For polygons with more than four corners, the optimal insertion point depends on the data; in higher-dimensional d + 2-vertex polytopes, the conformal characterizations do not generalize and a geometric characterization remains open.
Abstract
from arXiv · showhide
Triangulate a simple quadrilateral by connecting all vertices to an additional point. If the vertices carry values, the piecewise linear function can be assigned a Dirichlet energy. We show that the minimal Dirichlet energy as a function of the location of the inserted point is convex, and the location of the minimum is independent of the values at the corners - a quadrilateral has a discrete harmonic center, characterized by an equilibrium of currents across the inserted edges. It turns out that the fixed points of the Möbius involution swapping opposite corners of the quadrilateral are critical points of this energy, so the discrete harmonic center is Möbius-covariant. For tangential and cyclic quadrilaterals the center admits simple closed forms related to the circle centers. The center and its data-independence generalize to polytopes with d + 2 vertices in dimension d, but the conformal characterizations are special to four points in the plane.
1. Introduction
The paper studies Dirichlet-energy minimization for fan triangulations of quadrilaterals and identifies a unique, data-independent discrete harmonic center. This center is Möbius-covariant and has special geometric descriptions for circle-related quadrilaterals.
- Motivation: The work minimizes the Dirichlet energy of a piecewise linear function inside a quadrilateral using a fan triangulation from an inserted vertex.This extends the energy-based perspective on Delaunay triangulations from diagonal choice to inserted-point placement.
- Main contribution: The minimal energy is convex in the insertion point, making the optimal location unique and independent of the corner values.The resulting distinguished point is called the discrete harmonic center.
- Conformal characterization: The discrete harmonic center is Möbius-covariant because it is a fixed point of the Möbius involution exchanging opposite corners.For parallelograms, this specializes to the intersection of the diagonals.
- Proof strategy: Spoke currents balance at the inserted vertex, while the location gradient is expressed through currents weighted by averaged gradients.These current-based closure conditions provide the main proof tool.
- Special cases: For tangential quadrilaterals the center is the incenter, while for cyclic quadrilaterals it lies on the line through the circumcenter and diagonal intersection.The cyclic case also has a simple closed-form location.
- Scope: For polytopes with d + 2 vertices in dimension d, the center remains data-independent, but the conformal characterizations are special to four planar points.The center becomes data-dependent for more than d + 2 points in d dimensions.
2. Setup
The setup places an inserted vertex and scalar value inside the extended complex plane, connects it to four quadrilateral corners, and analyzes the resulting affine interpolant on four triangles. The admissible insertion region is the quadrilateral kernel, with spoke currents encoding gradient jumps across inserted edges.
- Setup: The quadrilateral corners z0, ..., z3 lie in the extended complex plane and carry real values f0, ..., f3; an inserted point z carries value u.The fan triangulation connects z to every corner.
- Admissible locations: The triangles tile the quadrilateral exactly when z lies in the kernel K where every signed area Ak is positive.For convex quadrilaterals, K equals Q; the kernel is also nonempty for non-convex quadrilaterals.
- Fan refinement: The fan consists of triangles Tk = (z, zk, zk+1), whose signed areas Ak and boundary edges ek determine the piecewise linear interpolant.Each triangle has a constant complex gradient gk.
- Spoke currents: Gradient differences across each spoke are orthogonal to that spoke and represented by real-valued spoke currents τk.The currents become central quantities for closure conditions governing the optimal value and location.
- Energy: The Dirichlet energy is built from the constant gradients on the fan triangles and is invariant under similarities applied to the geometry.Translation leaves areas and gradients unchanged, while scaling preserves each area-gradient product.
3. Optimal inserted value
The inserted value is optimized through the cotangent stiffness formulation of the fan energy, yielding a unique cotangent-weighted harmonic value. Its optimality is equivalently expressed by a zero cyclic sum of spoke currents.
- Energy formulation: The fan energy has the quadratic form ED = v⊤L(z)v, where L(z) is the real symmetric 5 × 5 cotangent stiffness matrix.The matrix is assembled from cotangent edge weights over the four triangles.
- Value minimization: The total spoke weight is strictly positive for admissible z, so the energy is a positive quadratic function of the inserted value u.This establishes a unique minimizer in u for each admissible location.
- Optimal inserted value: The minimizing inserted value is the cotangent-weighted average of the neighboring corner values.Eliminating u produces the reduced energy associated with the Schur complement.
- Closure condition: The optimal value is characterized by the cyclic current-balance condition Σk τk = 0.The value follows a linear closure condition, whereas the insertion location is determined by a quadratic non-holomorphic condition.
4. The minimizing location is independent of the values
The minimized Dirichlet energy separates affine and non-affine corner data, making the minimizing insertion location independent of the corner values. This defines a distinguished discrete harmonic center for each quadrilateral.
- Affine data: Affine corner data produce the affine interpolant at every insertion location, so the minimized energy and matrix expression are location-independent.Cotangent weights reproduce linear functions, yielding constant gradients on all four triangles.
- Data decomposition: Affine function values form a three-dimensional subspace of R4, whose orthogonal complement is the line spanned by the affine dependency vector n.The coefficients of n are signed areas of corner triples and alternate in sign for a convex quadrilateral.
- Data decomposition: There exist a symmetric positive semidefinite matrix L0 and scalar field ϕ, both independent of the corner data, that describe the minimized energy.The dependence on the data is isolated through the affine-dependency direction.
- Non-affine data: For non-affine data, the minimizing location is arg min_z∈K ϕ(z), so it is independent of the corner values.The reference point changes ϕ only by a constant offset, preserving its minimizer.
5. The minimizing location is unique
The minimized Dirichlet energy is convex in the insertion location, and its critical-point condition is expressed through a current-based differential. Consequently, the minimizing location is unique and governed by a quadratic closure condition rather than the linear condition determining the inserted value.
- Critical points: The gradient of the minimized energy is expressed through the spoke-current configuration and is identified with the discrete Hopf differential.The critical-point condition is H(z)=0.
- Critical points: The location condition is one order higher than the first-order condition Σ_k τ_k = 0 that determines the optimal inserted value.The value is fixed by a linear closure condition, whereas the location is fixed by a quadratic non-holomorphic one.
- Critical points: For any non-affine data vector, the critical points of the minimized energy are exactly the critical points of ϕ.A point satisfying H(z)=0 for one non-affine datum satisfies it for all data.
- Uniqueness: Convexity makes the optimal insertion location unique.The uniqueness follows from the convexity result for the minimized energy.
- Uniqueness: The minimized energy D(·;f) is convex on K, equivalently ϕ is convex.Each triangle energy has a quadratic numerator and positive affine area denominator, yielding joint convexity.
6. The minimizing location as a fixed point
For parallelograms, the energy-minimizing insertion is the diagonal intersection. For general quadrilaterals, fixed points of the opposite-corner Möbius involution are critical points, with the global minimum selected when it lies in the admissible kernel.
- Parallelograms: The optimal insertion location for a parallelogram is the intersection of its diagonals.
- Möbius involution: Every quadrilateral admits a Möbius involution σ exchanging opposite corners.The map satisfies σ(z0)=z2, σ(z1)=z3, σ(z2)=z0, and σ(z3)=z1.
- Möbius involution: Although σ generally does not preserve straight edges, its fixed points are critical points of the minimized energy for arbitrary quadrilaterals.
- Fixed-point characterization: Inverting at a fixed point z∗ maps the quadrilateral’s corners to a parallelogram, and the converse characterizes fixed points of σ.
- Current closure: At a fixed point, the spoke-current closure has alternating form τk = µ(−1)^k, which yields a critical point of the energy.
- Minimization: The energy D(z) is convex on the kernel K; when z∗ lies in K, it is the global minimum, while this fixed-point condition can fail to locate the constrained minimum otherwise.
- Möbius covariance: The fixed points z∗ are Möbius-covariant: transforming the corners by a Möbius map transforms z∗ by the same map.
7. Alternative characterizations
The optimal insertion has several equivalent geometric and potential-theoretic descriptions. These include tangency of opposite circumcircles, a dual-quadrilateral diagonal intersection, electrostatic equilibrium, and special circle-center formulas.
- Circumcircle tangency: Opposite circumcircles of the fan triangles meet tangentially at the optimal insertion point.
- Electrostatic characterization: With alternating unit charges at the corners, the fixed points of σ are electrostatic equilibria.
- Dual quadrilateral: Tangency of opposite fan circumcircles is equivalent to D(z)=z, where D(z) is the intersection of the dual quadrilateral’s diagonals.
- Complex potential: The associated holomorphic potential has derivative W′(z) = −R(z), and the zeros of R(z) are the fixed points of σ.
- Circle-related cases: For a tangential quadrilateral, the energy-optimal insertion point is the incenter.
- Hopf differential: The quadratic Hopf differential has double zeros at the two fixed points and double poles at the quadrilateral’s corners.
8. Special cases: Quadrilaterals related to circles
Circle-related quadrilaterals yield explicit descriptions of the discrete harmonic center: it is the incenter for tangential quadrilaterals and lies on a geometrically characterized line for cyclic ones.
- Tangential quadrilaterals: The energy-optimal insertion point of a tangential quadrilateral is its incenter.The incenter is selected as the minimum among the two electrostatic equilibria because tangential quadrilaterals are convex and contain it.
- Tangential quadrilaterals: At the incenter, the circumcircles of the fan triangles meet tangentially.This identifies a special tangential-quadrilateral configuration as an instance of a structure carried by every quadrilateral.
- Cyclic quadrilaterals: For a cyclic quadrilateral, the hyperbolic diagonals are circular arcs through opposite vertices meeting the circumcircle orthogonally.Their circles γ02 and γ13 intersect at the fixed points of the Möbius involution swapping opposite corners.
- Cyclic quadrilaterals: The circumcenter O, diagonal intersection P, and critical points z∗ and ˜z∗ lie on the radical line of γ02 and γ13.The radical-axis argument establishes the collinearity of these four points.
- Cyclic quadrilaterals: For cyclic quadrilaterals, the critical points z∗ and ˜z∗ admit expressions in terms of O, P, and the circumradius R.Their formulas follow from the ordering of P between the two critical points and intersecting-circle relations.
- Scope: The cyclic collinearity characterization does not extend to noncyclic quadrilaterals through the circumcenter of mass.Orthogonality of the circles is essential to the construction.
9. Discussion
The discussion distinguishes the discrete harmonic center from affine quadrilateral centers, identifies its four-point conformal character, and states limits of the theory beyond quadrilaterals.
- Discussion: The discrete harmonic center is Möbius-covariant rather than affine-covariant.It agrees with vertex or area centroids and the diagonal intersection only for parallelograms, and is unrelated to the circumcenter of mass.
- Discussion: For triangles, every insertion point gives the same energy because the piecewise linear interpolant is always affine.Degenerate quadrilateral limits can instead drive the insertion point toward the two collapsing corners.
- Discussion: In d dimensions, polytopes with d + 2 vertices retain a unique, data-independent optimal insertion point.However, none of the conformal characterizations generalize, and a geometric characterization remains open.
Appendix A. Mapping the corners of cyclic to bicentric quadrilaterals
The appendix normalizes a cyclic quadrilateral by its cross ratio, constructs a bicentric representative, and verifies the resulting Möbius correspondence.
- Normalization: The cyclic quadrilateral is normalized by computing its cross ratio λ and relabeling so that λ ≥ 2.When λ < 2, the labels are shifted and λ is replaced by λ/(λ − 1).
- Construction: The construction forms a tangential polygon from contact points.The contact chords are orthogonal, producing a bicentric quadrilateral.
- Construction: The normalized corners are p0 = −a + ib, p1 = i, p2 = a + ib, and p3 = −i.
- Verification: The constructed quadrilateral has cross ratio λ = 1 + 1/a^2.Preservation of the cross ratio ensures that the Möbius map sending three corners also sends the fourth correctly.