欧氏度量下特定Lₚ空间中最小化最大最近点距离的n点集选取问题的文献名称及算法问询

嘿，这个问题在几何优化和近似算法领域可是个经典议题，咱们来好好捋一捋：

一、问题的通用名称 #

你提出的这个问题正式叫做n-中心问题（n-center problem），也常被称为最优球覆盖问题的核心子问题（本质上是用n个以候选点为中心的欧氏球覆盖目标空间，最小化覆盖球的最大半径），部分文献也会称其为最小最大距离选址问题。

二、各特定空间的解与算法情况 #

1. 单位Lₚ球/球面（p∈{1,2,∞}，欧氏度量） #

p=2（欧氏球/球面）

• 对于单位欧氏球面（$|x|_2=1$），这个问题和**球面码（spherical codes）**是对偶问题：你的目标是最小化到点集的最大最近距离，等价于最大化点集中任意两点的最小距离（最优半径r对应的点集两点间距至少为2r）。小n的精确解对应正多面体顶点（比如n=4对应正四面体顶点，n=6对应正八面体顶点）；大n场景下没有通用精确解，常用近似算法：
  • 贪心最远点算法：每次选取当前距离已选点集最远的点加入，能保证得到2倍最优半径的近似解，实际表现往往更好。
  • k-means++初始化策略：和贪心算法逻辑一致，能快速得到高质量近似点集。
  • 多项式时间近似方案（PTAS）：针对欧氏空间设计，可在多项式时间内得到(1+ε)倍近似解，适合大n需求。
• 对于单位欧氏球（$|x|_2≤1$），小n的精确解同样利用对称性（比如n=1选球心，n=2选直径两端点）；大n时可参考球面的近似算法，或结合球内均匀划分的思路优化。

p=∞（超立方体球/球面）

单位L∞球是$[-1,1]^d$（d维），球面为$\max|x_i|=1$。

• 精确解：当n是d的幂次时，可将超立方体均匀划分为n个小超立方体，把每个小超立方体的中心作为候选点，此时最大最近距离为小超立方体对角线的一半。
• 近似算法：若n不是幂次，可采用贪心最远点算法，或基于网格划分的局部调整策略，小n场景也可通过整数规划求解。

p=1（交叉多面体球/球面）

单位L1球是$\sum|x_i|≤1$，球面为$\sum|x_i|=1$。

• 这个场景的精确解研究相对较少，通常利用空间的对称性选取候选点（比如交叉多面体顶点结合中间分点）。
• 近似算法优先选用贪心最远点算法，或基于对称区域划分的启发式方法。

2. 单位单纯形（$x≥0, x·1=1$） #

这个场景属于单纯形上的n-中心问题：

• 小n的精确解可通过几何对称性分析得到（比如n=1选单纯形重心，n=3选三个顶点时，最大最近距离为边长的一半）；
• 近似算法常用贪心最远点算法，小n场景也可通过凸优化或分支定界法求解精确解，大n时可结合蒙特卡洛采样加局部搜索优化。

三、文献与算法总结 #

• 核心术语：记住n-中心问题是最通用的名称，相关研究主要分布在几何优化、近似算法、选址理论领域。
• 精确算法：仅适用于低维空间、小n场景，依赖几何对称性分析、凸优化或分支定界法。
• 近似算法：贪心最远点算法是最常用的基础方案，k-means++、PTAS则分别针对不同规模需求提供更优的近似效果。

备注：内容来源于stack exchange，提问作者user76284