Identifying Extreme Points

2026-05-05 · Source: OR in an OB World · Field: Science & Research — Mathematics & Computational Sciences · Depth: Advanced, short

Summary

A recent blog post by Erwin Kalvelagen on "Convex hull models" discusses methods for identifying the extreme points of a finite point set's convex hull. The author of this analysis expands on Kalvelagen's observation that these problems often solve at the root node, suggesting they might be solvable as linear programs (LPs). The core idea involves expressing each point $p_i$ as a convex combination of all points in the set $P=\lbrace p_1,\dots,p_m\rbrace\subset \mathbb{R}^n$. By minimizing the coefficient $\lambda_i$ associated with $p_i$ in this combination, one can determine if $p_i$ is an extreme point: if the minimum $\lambda_i$ is 0, it is not extreme; if it is 1, it is extreme. The author implemented this logic in an R Markdown document using the lpSolve package to test two-dimensional point sets, demonstrating its effectiveness for identifying extreme points.

Key takeaway

For Data Scientists working with geometric algorithms or optimization, understanding that extreme points of a convex hull can be identified via a series of small Linear Programs (LPs) offers a computationally efficient alternative to more complex Mixed Integer Nonlinear Programming (MINLP) or Mixed Integer Linear Programming (MILP) models. You should consider implementing this LP-based approach, especially for high-dimensional or large datasets, to potentially reduce solution times and memory footprint compared to a single, larger optimization model.

Key insights

Extreme points of a finite set's convex hull can be identified using linear programming by minimizing a point's own coefficient.

Principles

• Extreme points cannot be convex combinations of other points.
• If $\lambda_i < 1$ exists, then $\lambda_i = 0$ also exists.

Method

To identify if point $p_i$ is extreme, minimize $\lambda_i$ subject to $p_i = \sum \lambda_k p_k$, $\sum \lambda_k = 1$, and $\lambda_k \ge 0$. A minimum $\lambda_i=0$ means non-extreme, while $\lambda_i=1$ means extreme.

In practice

• Use lpSolve in R for convex hull extreme point identification.
• Test with 2D point sets for easy visualization.
• Consider memory implications for single vs. sequential LP models.

Best for: Research Scientist, Data Scientist

Related on AIssential

• Convex hull models — Convex hull computation can be framed as an efficient optimization problem, potentially a linear program.
• Largest empty shapes — Finding largest empty shapes in point sets requires diverse optimization models depending on the shape.
• [Re-Upload] What is Linear Programming (LP)? (in 2 minutes) ***No Background Music*** — Linear Programming optimizes linear objectives under linear constraints, forming a polyhedral feasible set.
• A Gentle Introduction to Nonlinear Constrained Optimization with Piecewise Linear Approximations — Linearizing separable nonlinear programs via PWL approximations and SOS type 2 constraints enables efficient solution with LP/MIP solvers.
• Linear Regression Is Actually a Projection Problem, Part 1: The Geometric Intuition — Understanding vectors, dot products, and projections provides a geometric intuition for linear regression.
• Non-asymptotic quantisation of spherically symmetric distributions — This paper addresses the challenge of optimal quantisation in high dimensions ($d$), where Zador's theorem requires an astronomically large sample size ($n$) for its asymptotic behavior to be observed.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by OR in an OB World.