基于线性规划求解直线方程定义的凸多面体切比雪夫中心

要解决这个问题，核心是把直线定义的凸多面体转化为你已掌握的半平面不等式约束形式，再基于点到直线的距离构建线性规划模型，具体步骤如下：

1. 把直线方程转成半平面约束 #

凸多面体是若干直线划分出的半平面交集，首先得明确每条直线对应的、构成凸多面体边界的半平面方向：

• 如果凸多面体在直线 ( y = a_i x + b_i ) 的下方，对应的不等式为 ( y \leq a_i x + b_i )，整理成标准线性约束：( -a_i x + y \leq b_i )
• 如果凸多面体在直线的上方，对应的不等式为 ( y \geq a_i x + b_i )，整理成标准线性约束：( a_i x - y \leq -b_i )

所有约束最终都转化为 ( p_i x + q_i y \leq r_i ) 的形式——这正是你熟悉的处理场景。

2. 构建切比雪夫中心的线性规划模型 #

切比雪夫中心是凸多面体内到所有边界的最小距离最大的点 ((x_0, y_0))，我们设这个最大最小距离为 ( r )。

对于每个半平面约束 ( p_i x + q_i y \leq r_i )，点 ((x_0, y_0)) 到边界直线 ( p_i x + q_i y = r_i ) 的距离为：
[
\frac{r_i - p_i x_0 - q_i y_0}{\sqrt{p_i^2 + q_i^2}}
]
（因为点在凸多面体内，( p_i x_0 + q_i y_0 \leq r_i )，绝对值可直接去掉）

我们的目标是最大化 ( r )，同时要求该点到所有边界的距离都不小于 ( r )，因此线性规划模型为：

目标函数 #

max  r

约束条件（对所有半平面 ( i )） #

p_i x0 + q_i y0 + sqrt(p_i² + q_i²) * r ≤ r_i

这里 ( \sqrt{p_i² + q_i²} ) 是已知常数，所以约束都是线性的，完全符合线性规划的要求。

3. 求解线性规划 #

把目标函数和约束输入线性规划求解器，得到的 ( (x_0, y_0) ) 就是切比雪夫中心，( r ) 是该中心到所有边界的最小距离（即凸多面体的最大内切圆半径）。

示例演示 #

假设凸多面体由三条直线围成：

1. ( y = x + 1 )（凸多面体在下方，约束：( -x + y ≤ 1 )）
2. ( y = -x + 3 )（凸多面体在下方，约束：( x + y ≤ 3 )）
3. ( y = 0 )（凸多面体在上方，约束：( -y ≤ 0 )）

对应的线性规划约束为：

1. ( -x + y + \sqrt{2} r ≤ 1 )
2. ( x + y + \sqrt{2} r ≤ 3 )
3. ( -y + r ≤ 0 )

求解后即可得到该三角形的切比雪夫中心和最大内切圆半径。

内容的提问来源于stack exchange，提问作者legengary