Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces |
| |
Authors: | O Schwarzkopf M Sharir |
| |
Institution: | (1) Department of Computer Science, Pohang University of Science and Technology, Hyoja-Dong, Pohang 790—784, South Korea otfried@cs.ust.hk , KR;(2) School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel sharir@math.tau.ac.il and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA, US |
| |
Abstract: | Let Σ be a collection of n algebraic surface patches in of constant maximum degree b, such that the boundary of each surface consists of a constant number of algebraic arcs, each of degree at most b as well. We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement is O(n^{2+ɛ}), for any ɛ > 0, where the constant of proportionality depends on ɛ and on the maximum degree of the surfaces and of their boundaries. As an application, we obtain a near-quadratic motion-planning
algorithm for general systems with three degrees of freedom.
Received May 30, 1996, and in revised form February 18, 1997. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|