Loading...
Please wait, while we are loading the content...
Similar Documents
Constructing convex hulls of quadratic surface patches
| Content Provider | Semantic Scholar |
|---|---|
| Author | Hung, Chan Kwok Ierardi, Doug |
| Copyright Year | 1995 |
| Abstract | We study geometric duality and use modi ed de nitions to obtain good complexity upper bounds on and algorithms dealing with the convex hull of piecewise smooth manifolds in E Speci cally we show that the convex hull of a collection of N smooth algebraic surface patches of bounded degree with bounded number of similarly constrained subfaces in E has complexity O N for all and can be constructed in randomized expected time of the same complexity The dual construction also produces an O N logN algorithm for constructing the convex hull of an unordered collection of N algebraic curve segments and points in E From a practical point of view the duality arguments enable us to give a simple characterization of the convex hull of quadratic surface patches bor dered by an arbitrary number of segments of conic sections In this case it is shown how to obtain closed form parameterizations of the new surfaces which arise in the construction of the convex hull Algebraic overhead is reasonable involving only numerical computations and existing simpler algorithms for CSG Constructive Solid Geometry intersection may be employed in place of the asymptotically e cient yet more complicated al gorithm Point classi cation against the hull may be performed in time O N logN log N using a simple algorithm without explicit construction of the hull |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.usc.edu/assets/004/83265.pdf |
| Alternate Webpage(s) | https://www.cs.usc.edu/assets/004/83265.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
