Sammanfattning. Plane-sweep algoritmer bildar en ganska allmän strategi för tvådimensionella problem med beräkningsgeometri. Inga motsvarande allmänna rymdsvepalgoritmer för geometriska problem i 3-rymden är kända. Vi härleder koncept för sådana utrymme-sweep algoritmer som ger en effektiv lösning på problemet med att lösa varje set operation (union, skärningspunkt.... ) av två konvex polyhedra. Vår lösning matchar den mest kända tidslinjen för O(n log n), där n är det kombinerade antalet hörn av de två polyhedra.
I REF uppnås till exempel tids komplexiteten hos O(n log n) för beräkning av skärningspunkten mellan två konvexa polyhedra om deras ytor är pre-triangulerade.
Space sweep solves intersection of convex polyhedra
{'venue': 'Acta Informatica', 'journal': 'Acta Informatica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}