Navigating Weighted Regions with Scattered Skinny Tetrahedra
| Autor: | Siu-Wing Cheng, Jiongxin Jin, Man-Kwun Chiu, Antoine Vigneron |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
0102 computer and information sciences
02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Simplicial complex 0202 electrical engineering electronic engineering information engineering Computer Science::General Literature ComputingMilieux_MISCELLANEOUS Mathematics Connected component business.industry Computer Science::Information Retrieval Applied Mathematics Astrophysics::Instrumentation and Methods for Astrophysics Approximation algorithm Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Vertex (geometry) Running time Computational Mathematics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics 010201 computation theory & mathematics Shortest path problem ComputingMethodologies_DOCUMENTANDTEXTPROCESSING Tetrahedron 020201 artificial intelligence & image processing Geometry and Topology Telecommunications business |
| Zdroj: | International Journal of Computational Geometry & Applications. 27:13-32 |
| ISSN: | 1793-6357 0218-1959 |
| Popis: | We propose an algorithm for finding a [Formula: see text]-approximate shortest path through a weighted 3D simplicial complex [Formula: see text]. The weights are integers from the range [Formula: see text] and the vertices have integral coordinates. Let [Formula: see text] be the largest vertex coordinate magnitude, and let [Formula: see text] be the number of tetrahedra in [Formula: see text]. Let [Formula: see text] be some arbitrary constant. Let [Formula: see text] be the size of the largest connected component of tetrahedra whose aspect ratios exceed [Formula: see text]. There exists a constant [Formula: see text] dependent on [Formula: see text] but independent of [Formula: see text] such that if [Formula: see text], the running time of our algorithm is polynomial in [Formula: see text], [Formula: see text] and [Formula: see text]. If [Formula: see text], the running time reduces to [Formula: see text]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|