Question

Minimum Enclosing Rectangle / Minimum Bounding Box

二维平面的矩形，包围所有点。可令面积最小、令周长最小。

凸包，旋转卡尺。O(NlogN)。

http://cgm.cs.mcgill.ca/~orm/maer.html

http://mathoverflow.net/questions/23849/

UVa 819 10173 ICPC 5138

http://cgm.cs.mcgill.ca/~orm/mper.html

UVa 12307

Minimum Bounding Volume

三维空间的长方体，包围所有点，体积最小。

三维旋转卡尺？正确性不明。O(N^3)。

UVa 12308

Maximum Empty Rectangle

Largest Empty Rectangle among a Point Set. Jeet Chaudhuri, Subhas C. Nandy. 1999.

O(N^3)。

Maximum Empty Orthogonal Rectangle

二维平面的矩形，不含任何点，矩形摆正，面积最大。

平面边界四个角落补点，穷举每一点当作矩形左（与右）边界，然后依序扫描右方（与左方）的点作为右（左）边界，扫描过程中随时更新上下边界。另外，矩形的左右边界可能是平面的左右边界。O(N^2)。

Divide and Conquer。O(N*(logN)^3)。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.5774

UVa 10043

Maximum Weight Box

二维平面上有许多点，每个点有权重，有正有负。找到一个摆正的矩形，内部所有点的权重总和最大。

https://cs.uwaterloo.ca/~tmchan/optbox_cccg.pdf

O(N^2)。

Minimum Enclosing Square Annulus

二维平面的方环，包围所有点。可令宽度最小、令面积最小。

ICPC 6121

Circle

Minimum Enclosing Circle

二维平面的圆，包围所有点，面积暨周长暨半径最小。

一个圆包围所有点，半径相对伸缩后，一个点归属所有圆。

圆心位于 Farthest Point Voronoi Diagram 的顶点上。O(NlogN)。

半平面交集，randomized incremental method。平均 O(N)，最差 O(N^2)。

UVa 10005 11681

Minimum Bounding Sphere

三维空间的球，包围所有点，体积暨表面积暨半径最小。

Welzl's Algorithm。平均 O(N)。

http://www.inf.ethz.ch/personal/gaertner/miniball.html

UVa 10095

Minimum k Enclosing Circle

二维平面的圆，包围 k 个点，面积暨周长暨半径最小。

Order k Voronoi Diagram。O(NlogN + k^2 * N)。

二分搜寻半径 r。穷举每个点，作为圆边界，显然圆心与该点相距 r。旋转的扫描线，圆绕该点一圈。O(logR * N * NlogN)。

承上，只取邻点来扫描，以该点为中心，取正方形边长 4r 之内所有点，确保点数低于 k(16r²)/(πr²) < 5.1k。Range Tree。O(logR * N * (klogk + (logN)^2))。

ICPC 7488

Maximum Empty Circle / Maximum Inscribed Circle

二维平面的圆，不含所有点和边，面积暨周长暨半径最大。

一群点最大空圆：圆心位于 Voronoi Diagram 的顶点上。如果平面有边界，那麽圆心也可能在边上。O(NlogN)。

凸多边形最大内切圆：每条边同时往垂直方向等速内缩。每条边配合左右邻边的角平分线，就可求得消失所需距离。现在换个角度来看，不内缩了，改为预测最快消失的边，删除此边，左右邻边延长衔接于一点，就缩小问题范畴了。所有边放入二元树，按照消失顺序排序，每当删除一条边就更新二元树。O(NlogN)。

凸多边形最大内切圆：二分搜寻内切圆半径，以半平面交集验证。O(NlogR)。

UVa 11257 ICPC 3890

简单多边形最大内接圆。【待补文字】

正交多边形最大内接圆。【待补文字】

ICPC 2994

Minimum Enclosing Annulus

二维平面的环，内围外围圆心相同，包围所有点。可令宽度最小、令面积最小。

建立 Voronoi Diagram 与 Farthest Point Voronoi Diagram，穷举三种情况。O(N^2)。

一外三内：穷举外点；穷举圆心，即 Voronoi Diagram 的点。O(N^2)。
两外两内：穷举 Voronoi Diagram 的边，
　　　　　穷举 Farthest Point Voronoi Diagram 的边，
　　　　　两边求交点，作为圆心。O(N^2)。
三外一内：穷举内点；穷举圆心，即 Farthest Point Voronoi Diagram 的点。O(N^2)。

Maximum Empty Annulus

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.1095

Triangle

Minimum Enclosing Triangle

二维平面的三角形，包围所有点。可令面积最小、令周长最小。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.175.2381

Maximum Empty Triangle

二维平面的三角形，不含任何点，面积最大。

当平面没有边界，这个问题没有讨论意义；把三角形压扁、拉长，即不含任何点、面积无限大。

如果设定了三角形的角度范围，那麽就有讨论意义了。

如果给定的平面拥有一个长方形边界，然后多边形是凸的呢？
这个时候就不会有面积无限大的多边形了吧？

不是凸的形状，就只能採用“顶点属于给定的点集合”。
若是凸的形状（如三角形、长方形、凸多边形、圆形），
除了可以採用“顶点属于给定的点集合”，
也可以採用“边界碰到给定的点集合”。

这种时候就不知道如何命名了。

UVa 10112

Extremum Triangle

二维平面的三角形，一群点挑三点作为顶点。可令面积最小最大、令周长最小最大。

面积最小最大：点线对偶。O(N^2)。

http://3glab.cs.nthu.edu.tw/~spoon/courses/CS631100/Lecture09_handout.pdf

Convex Polygon

Minimum Enclosing Convex Polygon = Convex Hull

凸多边形，包围所有点，面积暨周长最小。

即“ Convex Hull ”。

Maximum Empty Convex Polygon
（Largest Empty Convex Subset）

凸多边形，不含任何点，一群点挑几个点作为顶点。可令顶点最多、令面积最大、令周长最大。

顶点最多：点线对偶，扫描线。O(N^3)。

Minimum Enclosing Convex k-gon

凸 k 边形，包围所有点，可令面积最小、令周长最小。

http://cs.smith.edu/classwiki/c/c8/Mitchell.MinPerim.pdf

Extremum Empty Convex k-gon
（Largest Empty Convex Subset）

凸 k 边形，不含任何点，一群点挑 k 个点作为顶点，可判断是否存在、令面积最小最大、令周长最小最大。

判断是否存在：NP-hard。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.5466

面积周长最小最大：O(k*N^3)。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.419.8207

面积周长最大：O((kN + NlogN) * logN)。运用“ SMAWK Algorithm ”得加速到 O(kN + NlogN)。

ICPC 2674

Extremum Convex k-gon

凸 k 边形，一群点挑 k 个点作为顶点。可判断是否存在、令面积最小最大、周长最小最大。

判断是否存在，即“ Erdős-Szekeres Conjecture ”。

演算法同上。

Extremum Convex Hull of k Points

凸多边形，边界暨内部恰有 k 个点。可判断是否存在、令面积最小最大、周长最小最大。

演算法同上。

Polygon

Minimum Simple Polygon

简单多边形，所有点作为顶点，可令面积最小、令边长最小。

NP-hard。

UVa 12386

Longest Segment in Simple Polygon

简单多边形，内部最长线段。

最长线段：必然碰到其中两个顶点，否则可以旋转线段变得更长。穷举两顶点，计算线段与多边形交点。O(N^3)。

最长对角线：O(N*(logN)^3)。

ICPC 4756

Maximum Convex Polygon in Simple Polygon
（Potato Peeling）

简单多边形，内部最大凸多边形。把凹凹凸凸削平。

O(N^7)。