Loading...
Please wait, while we are loading the content...
Similar Documents
Storing the Subdivision o f a Polyhedral Surface
| Content Provider | Semantic Scholar |
|---|---|
| Author | Moun, David M. Dobkin, David P. |
| Copyright Year | 2005 |
| Abstract | A common structure arising in computational geometry is the subdivision of a plane defined by the faces of a straight-line planar graph. We consider a natural generalization of this structure on a polyhedral surface. The regions of the subdivision are bounded by geodesics on the surface of the polyhedron. A method is given for representing such a subdivision that is efficient both with respect to space and the time required to answer a number of different queries involving the subdivision. For example, given a point x on the surface of the polyhedron, the region of the subdivision containing x can be determined in logarithmic time. If n denotes the number of edges in the polyhedron, m denotes the number of geodesics in the subdivision, and K denotes the number of intersections between edges and geodesics, then the space required by the data structure is O((n+m)log(n+m)), and the structure can be built in O(K + (n + m)log(n + m)) time. Combined with existing algorithms for computing Voronoi diagrams on the surface of polyhedra, this structure provides an efficient solution to the nearest-neighbor query problem on polyhedral surfaces. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://rd.springer.com/content/pdf/10.1007%2FBF02187877.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
