Traversal Graf untuk Optimasi SAT

Minimum fungsi support pada optimasi SAT terletak pada titik diskontinuitas di Gauss map, yaitu arah normal bidang muka poliedra.

Alih-alih mengevaluasi fungsi support penuh untuk setiap bidang, algoritma dioptimasi dengan traversa graf pada Gauss map sehingga hanya perlu satu evaluasi penuh dan selanjutnya cukup memperbarui simpul secara lokal saat melintasi busur.

Implementasi efektif memanfaatkan struktur data half-edge untuk menyimpan topologi simpul, busur, dan muka guna memudahkan penelusuran lintasan pada permukaan bola.

Pendekatan traversal graf ini terbukti 5–10× lebih cepat daripada SAT standar pada convex hull berwajah banyak, serta memberikan peningkatan kinerja pada kasus hull vs segitiga.