Bao lồi 3D
Dựng bao lồi của tập điểm trong không gian bằng thuật toán gia tăng O(n^2) với phép thử định hướng nguyên chính xác, tính diện tích, thể tích, xử lý suy biến và suy ra tam giác phân Delaunay qua phép nâng lên paraboloid.
Bao lồi 3D (3D convex hull) của điểm trong không gian là khối đa diện lồi nhỏ nhất chứa tất cả các điểm. Hình dung: bọc các điểm bằng một tấm màng co, khi màng co hết cỡ nó ôm sát các điểm ngoài cùng và tạo thành một đa diện có các mặt tam giác. Cách ngây thơ thử mọi bộ ba điểm làm mặt rồi kiểm tra điểm còn lại mất ; thuật toán gia tăng (incremental) trong bài này chỉ mất , đủ cho vài nghìn, và phiên bản gia tăng ngẫu nhiên với đồ thị xung đột đạt kỳ vọng. Từ bao lồi 3D ta tính được diện tích mặt, thể tích, và (qua phép nâng lên paraboloid) cả tam giác phân Delaunay trong mặt phẳng.
Nếu chưa quen bao lồi trên mặt phẳng, nên đọc trước Convex Hull (Bao lồi).
Ý tưởng / Trực giác
Tích có hướng và tích vô hướng trong 3D
Với hai vector và :
- Tích vô hướng (dot product) bằng : dương khi hai vector cùng phía, bằng khi vuông góc.
- Tích có hướng (cross product) là một vector vuông góc với cả và , có độ dài bằng diện tích hình bình hành dựng trên . Chiều của nó theo quy tắc bàn tay phải: nếu nhìn từ đầu mũi tên xuống thì quay sang ngược chiều kim đồng hồ.
Hệ quả: tam giác có pháp tuyến và diện tích .
Định hướng của một điểm so với một mặt (thể tích có dấu)
Đây là phép thử duy nhất mà thuật toán cần, tương tự phép thử "rẽ trái / rẽ phải" trong 2D:
- : nằm cùng phía với pháp tuyến của mặt .
- : nằm phía ngược lại.
- : bốn điểm đồng phẳng.
Giá trị tuyệt đối của nó bằng 6 lần thể tích tứ diện . Với tọa độ nguyên, đây là phép tính nguyên chính xác, không có sai số làm tròn: mọi quyết định của thuật toán đều đúng tuyệt đối.
Quy ước trong bài: mỗi mặt của bao được lưu sao cho pháp tuyến hướng ra ngoài, tức là nhìn từ ngoài vào, ba đỉnh đi ngược chiều kim đồng hồ. Khi đó một điểm nhìn thấy mặt khi và chỉ khi .
Thuật toán gia tăng: mặt nhìn thấy và đường chân trời
Dựng bao cho vài điểm đầu, rồi thêm lần lượt từng điểm :
- Nếu ở trong bao (không mặt nào thấy ): bao không đổi.
- Nếu ở ngoài: tưởng tượng đứng tại cầm đèn pin chiếu vào khối đa diện. Các mặt được chiếu sáng là mặt nhìn thấy (visible faces); chúng tạo thành một vùng liền trên bề mặt. Biên của vùng sáng là một chu trình cạnh gọi là đường chân trời (horizon). Ta xóa mọi mặt nhìn thấy và nối với từng cạnh chân trời, tạo một "nón" các mặt tam giác mới.
Vì sao đúng? Bao mới gồm hai phần: những mặt cũ không thấy (chúng vẫn là mặt tựa, nằm phía trong của chúng) và những mặt mới đi qua . Một mặt mới qua phải tựa lên bao cũ dọc một cạnh mà một bên được chiếu sáng, một bên không: chính là cạnh chân trời. Mặt nhìn thấy bị loại vì nằm ngoài mặt phẳng của chúng, chúng không còn là mặt tựa.
Cài đặt cạnh chân trời rất gọn nhờ cạnh có hướng: mỗi cạnh thuộc đúng một mặt (mặt kề bên kia chứa cạnh ngược ). Cạnh của một mặt nhìn thấy là cạnh chân trời khi và chỉ khi mặt chứa không nhìn thấy. Mặt mới là , tự động đúng chiều hướng ra ngoài.
Ví dụ chạy tay
Bắt đầu từ tứ diện , , , rồi thêm lần lượt , , .
Bước 0: tứ diện ban đầu. Bốn mặt, định hướng ra ngoài (đỉnh thứ tư cho ):
| Mặt | Pháp tuyến ra ngoài | Mặt phẳng |
|---|---|---|
Thể tích .
Bước 1: thêm . Tính với từng mặt:
| Mặt | Nhìn thấy? | |
|---|---|---|
| không | ||
| không | ||
| không | ||
| có |
Chỉ được chiếu sáng, nên chân trời là ba cạnh của nó: , , . Xóa , thêm ba mặt , , .
graph 5 9 1 2 1 3 1 4 2 3 3 4 4 2 5 2 5 3 5 4 name 1 A name 2 B name 3 C name 4 D name 5 P pos 1 100 200 pos 2 260 200 pos 3 40 150 pos 4 100 40 pos 5 230 70 step Tứ diện ABCD và điểm mới P highlight gray 5-2 5-3 5-4 highlight orange 5 step Mặt BCD nhìn thấy P: ba cạnh của nó là đường chân trời highlight red 2-3 3-4 4-2 step Xóa BCD, nối P với các cạnh chân trời: thêm BCP, CDP, DBP highlight green 5-2 5-3 5-4
Thể tích tăng đúng bằng tổng dương chia : , tổng thành . Diện tích mặt (mỗi mặt mới có pháp tuyến độ dài ).
Bước 2: thêm . Cả sáu mặt cho (ba mặt trục cho , ba mặt mới cho ). Không mặt nào nhìn thấy: ở trong, bỏ qua.
Bước 3: thêm . Lần này hai mặt sáng:
| Mặt | Nhìn thấy? | |
|---|---|---|
| có | ||
| , , , | không | |
| có |
Hai mặt sáng (cạnh , , ) và (cạnh , , ) chung cạnh nên cạnh này không thuộc chân trời (cạnh ngược của nó cũng sáng). Chân trời là chu trình , bốn mặt mới: , , , .
Trước: 6 mặt, thể tích 24
Sáng: ACB, BCP (chung cạnh BC -> không phải chân trời)
Chân trời: A->C, C->P, P->B, B->A
Sau: 6 - 2 + 4 = 8 mặt, thể tích 24 + (32 + 40)/6 = 36
Kiểm tra: đỉnh , đa diện tam giác hóa có mặt. Chương trình bên dưới in đúng faces 8, area 66.974691, volume 36.000000 cho input này.
Cài đặt
Input: , rồi dòng tọa độ nguyên (). Output: số mặt tam giác, diện tích mặt và thể tích của bao.
Các bước: bỏ điểm trùng; tìm điểm không đồng phẳng làm tứ diện ban đầu; thêm từng điểm còn lại như trên. Mảng owner[u*n + v] lưu mặt đang chứa cạnh có hướng . Thể tích tính bằng công thức phân rã từ gốc tọa độ: , một tổng nguyên chính xác.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
struct P3 {
ll x, y, z;
P3 operator-(const P3& o) const { return {x - o.x, y - o.y, z - o.z}; }
bool operator<(const P3& o) const { return tie(x, y, z) < tie(o.x, o.y, o.z); }
bool operator==(const P3& o) const { return x == o.x && y == o.y && z == o.z; }
};
// Cross product (components fit in long long for |coord| <= 1e6).
P3 cross(const P3& a, const P3& b) {
return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x};
}
// Dot product in __int128: each term can reach ~1e19.
lll dot(const P3& a, const P3& b) {
return (lll)a.x * b.x + (lll)a.y * b.y + (lll)a.z * b.z;
}
// Signed volume x6 of tetrahedron (a,b,c,d): > 0 if d is on the side
// the normal (b-a)x(c-a) points to.
lll orient(const P3& a, const P3& b, const P3& c, const P3& d) {
return dot(cross(b - a, c - a), d - a);
}
struct Face { int a, b, c; };
int main() {
int n;
scanf("%d", &n);
vector<P3> p(n);
for (auto& q : p) scanf("%lld %lld %lld", &q.x, &q.y, &q.z);
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
n = p.size();
// Find 4 points that are not coplanar.
int i1 = -1, i2 = -1, i3 = -1;
for (int i = 1; i < n && i1 < 0; i++) i1 = i;
for (int i = 1; i < n && i1 >= 0 && i2 < 0; i++) {
P3 c = cross(p[i1] - p[0], p[i] - p[0]);
if (c.x || c.y || c.z) i2 = i;
}
for (int i = 1; i < n && i2 >= 0 && i3 < 0; i++)
if (orient(p[0], p[i1], p[i2], p[i]) != 0) i3 = i;
if (i3 < 0) { puts("degenerate (all points coplanar)"); return 0; }
// owner[a*n+b] = index of the alive face containing directed edge a->b.
vector<int> owner((size_t)n * n, -1);
vector<Face> faces;
auto addFace = [&](int a, int b, int c) {
int id = faces.size();
faces.push_back({a, b, c});
owner[(size_t)a * n + b] = owner[(size_t)b * n + c] = owner[(size_t)c * n + a] = id;
};
// Initial tetrahedron, each face oriented so the 4th vertex is behind it.
int t[4] = {0, i1, i2, i3};
for (int k = 0; k < 4; k++) {
int a = t[(k + 1) % 4], b = t[(k + 2) % 4], c = t[(k + 3) % 4], d = t[k];
if (orient(p[a], p[b], p[c], p[d]) > 0) swap(b, c);
addFace(a, b, c);
}
vector<int> alive = {0, 1, 2, 3};
vector<char> vis;
for (int i = 0; i < n; i++) {
if (i == 0 || i == i1 || i == i2 || i == i3) continue;
vis.assign(faces.size(), 0);
bool any = false;
for (int f : alive) {
const Face& F = faces[f];
if (orient(p[F.a], p[F.b], p[F.c], p[i]) > 0) vis[f] = 1, any = true;
}
if (!any) continue; // inside or on the hull: nothing changes
// Horizon: edge a->b of a visible face whose twin b->a is not visible.
vector<pair<int, int>> horizon;
vector<int> keep;
for (int f : alive) {
if (!vis[f]) { keep.push_back(f); continue; }
int v[3] = {faces[f].a, faces[f].b, faces[f].c};
for (int k = 0; k < 3; k++) {
int a = v[k], b = v[(k + 1) % 3];
if (!vis[owner[(size_t)b * n + a]]) horizon.push_back({a, b});
}
}
for (auto [a, b] : horizon) { // cone from p[i] over the horizon
keep.push_back(faces.size());
addFace(a, b, i);
}
alive = keep;
}
double area = 0;
lll vol6 = 0;
for (int f : alive) {
const P3 &A = p[faces[f].a], &B = p[faces[f].b], &C = p[faces[f].c];
P3 c = cross(B - A, C - A);
area += sqrt((double)dot(c, c)) / 2;
vol6 += dot(A, cross(B, C)); // signed volume of (O,A,B,C) x6
}
printf("faces %d\n", (int)alive.size());
printf("area %.6f\n", area);
printf("volume %.6f\n", (double)vol6 / 6);
}
import sys
from math import sqrt
def sub(a, b):
return (a[0] - b[0], a[1] - b[1], a[2] - b[2])
def cross(a, b):
return (a[1] * b[2] - a[2] * b[1],
a[2] * b[0] - a[0] * b[2],
a[0] * b[1] - a[1] * b[0])
def dot(a, b):
return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
def orient(a, b, c, d):
# Signed volume x6: > 0 if d is on the side the normal of (a,b,c) points to.
return dot(cross(sub(b, a), sub(c, a)), sub(d, a))
def hull3d(pts):
p = sorted(set(pts))
n = len(p)
i1 = 1 if n > 1 else None
i2 = next((i for i in range(1, n) if i1 is not None
and cross(sub(p[i1], p[0]), sub(p[i], p[0])) != (0, 0, 0)), None)
i3 = next((i for i in range(1, n) if i2 is not None
and orient(p[0], p[i1], p[i2], p[i]) != 0), None)
if i3 is None:
return None, p
owner = {} # directed edge (a, b) -> face id
faces = []
def add_face(a, b, c):
faces.append((a, b, c))
fid = len(faces) - 1
owner[(a, b)] = owner[(b, c)] = owner[(c, a)] = fid
return fid
t = [0, i1, i2, i3]
alive = []
for k in range(4):
a, b, c, d = t[(k + 1) % 4], t[(k + 2) % 4], t[(k + 3) % 4], t[k]
if orient(p[a], p[b], p[c], p[d]) > 0:
b, c = c, b
alive.append(add_face(a, b, c))
for i in range(n):
if i in t:
continue
vis = {f for f in alive
if orient(p[faces[f][0]], p[faces[f][1]], p[faces[f][2]], p[i]) > 0}
if not vis:
continue
keep = [f for f in alive if f not in vis]
for f in vis:
a, b, c = faces[f]
for u, v in ((a, b), (b, c), (c, a)):
if owner[(v, u)] not in vis: # horizon edge
keep.append(add_face(u, v, i))
alive = keep
return [faces[f] for f in alive], p
def main():
data = sys.stdin.read().split()
n = int(data[0])
pts = [tuple(map(int, data[1 + 3 * i: 4 + 3 * i])) for i in range(n)]
faces, p = hull3d(pts)
if faces is None:
print("degenerate (all points coplanar)")
return
area = 0.0
vol6 = 0
for a, b, c in faces:
cr = cross(sub(p[b], p[a]), sub(p[c], p[a]))
area += sqrt(dot(cr, cr)) / 2
vol6 += dot(p[a], cross(p[b], p[c]))
print("faces", len(faces))
print("area %.6f" % area)
print("volume %.6f" % (vol6 / 6))
main()
Input của ví dụ chạy tay và output:
7
0 0 0
4 0 0
0 4 0
0 0 4
3 3 3
1 1 1
5 1 -2
faces 8
area 66.974691
volume 36.000000
Hai chương trình đã được đối chiếu với một lời giải vét cạn (với mỗi bộ ba điểm, kiểm tra mọi điểm nằm cùng một phía; gom các mặt phẳng tựa, tính diện tích đa giác phẳng trên từng mặt phẳng) trên 1800 bộ test ngẫu nhiên, gồm cả tọa độ trong (rất nhiều điểm đồng phẳng, thẳng hàng), toàn bộ đồng phẳng và toàn bộ thẳng hàng. Với điểm trên mặt cầu bán kính (mọi điểm đều nằm trên bao, trường hợp nặng nhất), bản C++ chạy khoảng giây.
Độ phức tạp
- Thời gian : mỗi lần thêm điểm, ta duyệt mọi mặt đang sống để tìm mặt nhìn thấy. Theo công thức Euler, đa diện tam giác hóa có đỉnh thì có mặt, nên mỗi bước , cả thuật toán . Số mặt mới tạo ra mỗi bước bằng số cạnh chân trời, tổng cộng cũng trong trường hợp xấu.
- Bộ nhớ: bảng
ownerkích thước số nguyên (với khoảng MB). Nếu giới hạn bộ nhớ chặt, thay bằngunordered_maptheo khóa , hoặc lưu cho mỗi mặt chỉ số ba mặt kề, khi đó bộ nhớ cộng với danh sách mặt đã tạo. - Bản Python cùng thuật toán nhưng chậm hơn trên lần ( điểm trên mặt cầu mất khoảng giây), dùng để hiểu và kiểm tra với vài trăm.
Gia tăng ngẫu nhiên: kỳ vọng
Chỗ tốn kém của bản là tìm mặt nhìn thấy bằng cách duyệt hết mọi mặt. Bản nhanh (Clarkson và Shor) làm như sau:
- Trộn ngẫu nhiên thứ tự các điểm.
- Duy trì đồ thị xung đột (conflict graph): với mỗi điểm chưa thêm , lưu một mặt hiện tại mà nhìn thấy (hoặc "ở trong"); với mỗi mặt, lưu danh sách điểm chưa thêm đang nhìn thấy nó.
- Khi thêm : mặt xung đột của cho ngay một mặt sáng, từ đó loang (BFS/DFS qua mặt kề) để lấy cả vùng sáng và chân trời, chỉ tốn thời gian tỉ lệ với số mặt bị xóa.
- Với mỗi mặt mới dựng trên cạnh chân trời , các điểm có thể thấy nó chỉ nằm trong danh sách xung đột của hai mặt cũ kề cạnh (mặt sáng bị xóa và mặt tối còn lại). Ta chỉ kiểm tra lại những điểm đó.
Phân tích ngược (backward analysis), giống thuật toán đường tròn bao nhỏ nhất trong Thuật toán ngẫu nhiên: với thứ tự ngẫu nhiên, số mặt mới tạo ở bước có kỳ vọng (bằng bậc trung bình của một đỉnh ngẫu nhiên, ), và tổng công việc cập nhật xung đột có kỳ vọng . Trong thi đấu, bản thường đủ; bản này cần khi .
Suy biến: đồng phẳng, thẳng hàng, nhiễu loạn
- Ít hơn 4 điểm không đồng phẳng. Nếu mọi điểm thẳng hàng hoặc đồng phẳng thì bao là đoạn thẳng hoặc đa giác phẳng, thể tích . Code trên báo
degenerate; nếu đề cần diện tích của "đa giác phẳng" đó, chiếu các điểm xuống mặt phẳng tọa độ ứng với thành phần pháp tuyến lớn nhất rồi dùng bao lồi 2D (diện tích chia cho để bù phép chiếu). - Điểm nằm trên một mặt hoặc trên phần kéo dài của mặt. Dùng điều kiện chặt cho "nhìn thấy". Điểm nằm đúng trên một mặt (orient ) không làm mặt sáng, nên bị bỏ qua khi nó nằm trong mặt đó; khi nằm ngoài biên mặt, một mặt kề sẽ thấy nó chặt và thuật toán vẫn đúng. Hệ quả: một mặt phẳng của đa diện thật (ví dụ mặt vuông của khối lập phương) có thể bị chia thành nhiều tam giác đồng phẳng. Diện tích và thể tích vẫn đúng, nhưng số mặt tam giác không phải số mặt thật của đa diện.
- Đếm mặt thật. Gộp các tam giác kề nhau có pháp tuyến cùng phương (tích có hướng hai pháp tuyến bằng và tích vô hướng dương), ví dụ bằng DSU trên các cạnh có hai mặt đồng phẳng.
- Nhiễu loạn (perturbation). Một cách xử lý suy biến là dịch mỗi điểm một lượng rất nhỏ để không còn bốn điểm đồng phẳng. Làm bằng số thực ngẫu nhiên (cỡ ) thì dễ cài nhưng mất tính chính xác và có thể sinh mặt "mảnh" sai. Cách đúng là nhiễu loạn ký hiệu (symbolic perturbation, ví dụ Simulation of Simplicity): coi tọa độ điểm là với vô cùng bé, khi thì quyết định dấu theo hệ số của lũy thừa nhỏ nhất. Với tọa độ nguyên và điều kiện chặt như trên, thường không cần nhiễu loạn để tính diện tích, thể tích.
Ứng dụng: diện tích, thể tích, Delaunay qua paraboloid
Diện tích và thể tích. Diện tích mặt . Thể tích , tổng các tứ diện có dấu từ gốc tới từng mặt: phần tứ diện nằm ngoài khối bị trừ đi đúng nhờ dấu, nên công thức đúng cho mọi vị trí của . Trọng tâm khối cũng tính được tương tự (trọng tâm từng tứ diện, trọng số là thể tích có dấu).
Tam giác phân Delaunay bằng phép nâng (lifting). Nâng mỗi điểm trên mặt phẳng lên paraboloid: . Khi đó:
Điểm nằm trong đường tròn ngoại tiếp tam giác (định hướng ngược chiều kim đồng hồ) khi và chỉ khi điểm nâng nằm dưới mặt phẳng qua .
Lý do: giao của một mặt phẳng với paraboloid chiếu xuống mặt phẳng là đường tròn ; phần paraboloid nằm dưới mặt phẳng chiếu xuống đúng phần trong đường tròn. Do đó các mặt của bao dưới (mặt có pháp tuyến ra ngoài với thành phần ) chiếu xuống chính là các tam giác Delaunay: không điểm nào nằm trong đường tròn ngoại tiếp của chúng. Phép thử "in-circle" quen thuộc thực chất là của bốn điểm đã nâng.
Ví dụ: điểm nâng thành độ cao . Chạy hull3d trên các điểm nâng được mặt: mặt dưới chính là tam giác Delaunay chung đỉnh , mặt trên là hai nửa của hình vuông (bốn góc đồng phẳng sau khi nâng, đúng vì chúng cùng nằm trên một đường tròn). Bao trên cho tam giác phân "Delaunay xa nhất" (farthest-point Delaunay). Chi tiết về Delaunay, Voronoi và cách dùng xem Delaunay và Voronoi.
Phiên bản 1D của cùng ý tưởng: nâng biến bài toán về parabol thành bài toán bao lồi 2D (xem bài uparab ở dưới).
⚠️ Lỗi thường gặp
- Tràn số trong
orient. Hiệu tọa độ tới , mỗi số hạng của định thức tới , tổng có thể vượt củalong long. Triệu chứng: bao sai lặt vặt trên test tọa độ lớn. Cách tránh: tích vô hướng cuối cùng dùng__int128(như code), hoặc đảm bảo . - Dùng số thực và epsilon cho phép thử định hướng. Sai số làm một điểm "vừa thấy vừa không thấy" mặt kề, vùng sáng không liền, chân trời không khép kín, bao bị thủng (số mặt lệch khỏi , thể tích âm). Với input nguyên, luôn tính định hướng bằng số nguyên chính xác; chỉ đổi sang
doubleở bước cuối (căn bậc hai cho diện tích). - Tứ diện ban đầu suy biến. Lấy đại điểm đầu tiên mà chúng đồng phẳng thì mọi mặt có "pháp tuyến ra ngoài" sai chiều. Phải tìm lần lượt: điểm khác , điểm không thẳng hàng, điểm không đồng phẳng; và nhớ bỏ điểm trùng trước.
- Định hướng mặt không nhất quán. Mặt mới phải là với là cạnh của mặt sáng (không phải ). Đảo chiều làm pháp tuyến hướng vào trong, ở bước sau mặt đó "thấy" gần như mọi điểm. Kiểm tra nhanh: tổng thể tích có dấu phải dương và .
- Dùng thay cho khi xét nhìn thấy. Với điều kiện không chặt, một điểm đồng phẳng với một mặt làm mặt đó sáng, có thể tạo mặt suy biến diện tích (ba điểm thẳng hàng) và phá cấu trúc cạnh kề. Dùng điều kiện chặt.
- Đếm số mặt tam giác rồi coi là số mặt đa diện. Khi có điểm đồng phẳng, một mặt thật bị chia thành nhiều tam giác (khối lập phương thêm tâm mặt trên ra tam giác thay vì mặt vuông). Nếu đề hỏi số mặt, phải gộp các tam giác đồng phẳng kề nhau.
- Quên trộn ở bản . Thuật toán gia tăng ngẫu nhiên với input theo thứ tự xấu (ví dụ điểm trên mặt cầu sắp theo độ cao) thoái hóa về .
Biến thể / Mở rộng
- Bao lồi 2D: cùng tư tưởng nhưng đơn giản hơn nhiều nhờ sắp xếp, xem Convex Hull (Bao lồi).
- Delaunay và Voronoi: tam giác phân Delaunay là bao dưới của các điểm nâng, sơ đồ Voronoi là đối ngẫu của nó, xem Delaunay và Voronoi.
- Giao các nửa không gian: theo đối ngẫu điểm và mặt phẳng, giao của nửa không gian chứa một điểm trong biết trước tương ứng với bao lồi 3D của các điểm đối ngẫu.
- Khoảng cách, va chạm giữa hai khối lồi: sau khi có bao, khoảng cách nhỏ nhất giữa hai đa diện lồi tính bằng các thuật toán như GJK; khoảng cách từ điểm trong tới bề mặt là khoảng cách tới các mặt phẳng mặt.
- Các kỹ thuật hình học khác trong mục Hình học.
Bài tập luyện
Kho bài CTOJ hiện chưa có bài yêu cầu dựng bao lồi 3D trực tiếp. Các bài dưới đây luyện những mảnh ghép của trang này: phép tính vector 3D chính xác trên số nguyên, chiếu điểm trong không gian bằng tích có hướng và tích vô hướng, và phép nâng lên parabol.
- Khôi phục khối lập phương (rstcube) (Rất khó) Duyệt hoán vị tọa độ của đỉnh rồi kiểm tra có tạo khối lập phương; cần ba vector cạnh từ một đỉnh có độ dài bằng nhau và tích vô hướng đôi một bằng , tính hoàn toàn trên số nguyên.
- Tia laser trong thực tại song song (laserray) (Chuyên gia) Chiếu các điểm 3D lên mặt phẳng vuông góc với một vector pháp tuyến, dựng cơ sở của mặt phẳng bằng tích có hướng, rồi tìm đường tròn bao nhỏ nhất của hình chiếu.
- Parabol chữ U (uparab) (Chuyên gia) Đổi biến biến parabol thành đường thẳng; đếm parabol "rỗng" chính là đếm cạnh của bao lồi trên, phiên bản một chiều thấp hơn của phép nâng Delaunay.
Bình luận