Lemma 28, p. 24 — moving two points towards each other does not increase their total distance to a third, strictly if not collinear
ProvedLearnAugFL.CMP.lemma_28convexityeuclidean-geometryfacility-locationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be three distinct points of the Euclidean plane with Euclidean distance , and let . Then
and the inequality is strict when are not collinear.
This convexity fact is what makes clustering two points on a half-axis strictly decrease the optimal cost when the optimum is off the axes (Lemma 15).
Preamble
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
Formal statement
namespace LearnAugFL.CMP
theorem lemma_28 (p₁ p₂ p₃ : Pt) (h12 : p₁ ≠ p₂) (h13 : p₁ ≠ p₃) (h23 : p₂ ≠ p₃)
(ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1) :
dist (p₁ + ε • (p₂ - p₁)) p₃ + dist (p₂ + ε • (p₁ - p₂)) p₃ ≤ dist p₁ p₃ + dist p₂ p₃ ∧
(¬ Collinear ℝ ({p₁, p₂, p₃} : Set Pt) →
dist (p₁ + ε • (p₂ - p₁)) p₃ + dist (p₂ + ε • (p₁ - p₂)) p₃ < dist p₁ p₃ + dist p₂ p₃) := by sorry
end LearnAugFL.CMP
Source
Agrawal, Balkanski, Gkatzelis, Ou & Tan, Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location, arXiv:2204.01120v1, Lemma 28, p. 24
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.