Sel terbesar dalam suatu pengaturan

10

Q . Apa kompleksitas menemukan sel terikat volume terbesar dalam pengaturan hiperplanes dalam dimensi d ?nd

Saya merasa saya harus tahu ini ... Tapi saya tidak menemukan referensi yang pasti.

Apakah itu ? Bagaimana dengan spesialisasi d = 2 : Area sel terikat terbesar dalam susunan garis?Ω(nd)d=2

Joseph O'Rourke
sumber

Jawaban:

6

O(nd)1QCα1/n2m=(logn)/αQPCPO((n2/3m2/3+n+m)polylog)

αO((n+1/α+n2/3/α2/3)polylogn)αQ

Sariel Har-Peled
sumber
1
α1/n2