标签:计算几何
6 个条目
-
概念 凸包与凸壳
凸组合、凸包与下凸壳;支撑线和线性函数 Y-KX 的最小值在凸壳顶点取得。
2026-11-13 -
平面完全图边权为曼哈顿距离;算法一用 8 个八分圆候选边 + Kruskal,算法二用四象限 Borůvka。
2026-11-12 -
题目 矩形并
给定若干轴对齐矩形,求并的面积和周长;按 x 扫描,用线段树维护 y 方向覆盖长度与连通分量数。
2026-11-12 -
点集的三角剖分,使每个三角形的外接圆内部不含其它点;二维有 O(n) 条边,是 EMST 的母图,并与 Voronoi 图对偶。
2026-11-10 -
二维 Delaunay 三角剖分的分治构造:按 x 分治,递归构造两侧后合并上下公切线之间的跨边,O(n log n)。
2026-11-10 -
平面点集的完全图边权为欧氏距离;用 Delaunay 三角剖分 + Kruskal 在 O(n log n) 时间求 MST。
2026-11-10