Determining the separation of preprocessed polyhedra – A unified approach. (English) Zbl 0765.68205
Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 400-413 (1990).
Summary: [For the entire collection see Zbl 0758.00017.]
We show how (now familiar) hierarchical representations of (convex) polyhedra can be used to answer various separation queries efficiently (in a number of cases, optimally). Our emphasis is:
i) the uniform treatment of polyhedra separation problems,
ii) the use of hierarchical representations of primitive objects to provide implicit representations of composite or transformed objects, and
iii) applications to natural problems in graphics and robotics.
Among the specific results is an \(O(\log| P|\cdot\log| Q|)\) algorithm for determining the separation of polyhedra \(P\) and \(Q\) (which have been individually preprocessed in at most linear time).
We show how (now familiar) hierarchical representations of (convex) polyhedra can be used to answer various separation queries efficiently (in a number of cases, optimally). Our emphasis is:
i) the uniform treatment of polyhedra separation problems,
ii) the use of hierarchical representations of primitive objects to provide implicit representations of composite or transformed objects, and
iii) applications to natural problems in graphics and robotics.
Among the specific results is an \(O(\log| P|\cdot\log| Q|)\) algorithm for determining the separation of polyhedra \(P\) and \(Q\) (which have been individually preprocessed in at most linear time).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
