# An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2013-06-01

AUTHORS ABSTRACT

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal D$$\end{document}, consisting of n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} tetrahedra with positive weights, and a real number ε∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon \in (0,1)$$\end{document}, our algorithm constructs paths in D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal D$$\end{document} from a fixed source vertex to all vertices of D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal D$$\end{document}, the costs of which are at most 1+ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1+\varepsilon$$\end{document} times the costs of (weighted) shortest paths, in O(C(D)nε2.5lognεlog31ε)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$$\end{document} time, where C(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{C }(\mathcal D )$$\end{document} is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions. More... »

PAGES

124-184

### References to SciGraph publications

• 2001-12-04. BUSHWHACK: An Approximation Algorithm for Minimal Paths through Pseudo-Euclidean Spaces in ALGORITHMS AND COMPUTATION
• 2003-11-05. Pseudo Approximation Algorithms with Applications to Optimal Motion Planning in DISCRETE & COMPUTATIONAL GEOMETRY
• 2006. A Framework for Working with Digitized Cultural Heritage Artifacts in COMPUTER AND INFORMATION SCIENCES – ISCIS 2006
• 2001-01. Approximating Shortest Paths on Weighted Polyhedral Surfaces in ALGORITHMICA
• 1988-06-01. The algebraic degree of geometric optimization problems in DISCRETE & COMPUTATIONAL GEOMETRY
• 1993. Automatic Mesh Partitioning in GRAPH THEORY AND SPARSE MATRIX COMPUTATION
• 1989. Concrete and Abstract Voronoi Diagrams in NONE
• 2009-07-07. Algorithms for Approximate Shortest Path Queries on Weighted Polyhedral Surfaces in DISCRETE & COMPUTATIONAL GEOMETRY
• 2004-01-23. Movement Planning in the Presence of Flows in ALGORITHMICA
• ### Journal

TITLE

Discrete & Computational Geometry

ISSUE

1

VOLUME

50

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00454-013-9486-0

DOI

http://dx.doi.org/10.1007/s00454-013-9486-0

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1018053658

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Bulgarian Academy of Sciences, IPP, Acad. G. Bonchev Str. Bl. 25-A, 1113, Sofia, Bulgaria",
"id": "http://www.grid.ac/institutes/grid.424859.6",
"name": [
"Bulgarian Academy of Sciences, IPP, Acad. G. Bonchev Str. Bl. 25-A, 1113, Sofia, Bulgaria"
],
"type": "Organization"
},
"familyName": "Aleksandrov",
"givenName": "Lyudmil",
"id": "sg:person.012737765445.28",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012737765445.28"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Los Alamos National Laboratory, 87545, Los Alamos, NM, USA",
"id": "http://www.grid.ac/institutes/grid.148313.c",
"name": [
"Los Alamos National Laboratory, 87545, Los Alamos, NM, USA"
],
"type": "Organization"
},
"familyName": "Djidjev",
"givenName": "Hristo",
"id": "sg:person.014017262276.55",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014017262276.55"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "School of Computer Science, Carleton University, K1S5B6, Ottawa, ON, Canada",
"id": "http://www.grid.ac/institutes/grid.34428.39",
"name": [
"School of Computer Science, Carleton University, K1S5B6, Ottawa, ON, Canada"
],
"type": "Organization"
},
"familyName": "Maheshwari",
"givenName": "Anil",
"id": "sg:person.012050257432.53",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050257432.53"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "School of Computer Science, Carleton University, K1S5B6, Ottawa, ON, Canada",
"id": "http://www.grid.ac/institutes/grid.34428.39",
"name": [
"School of Computer Science, Carleton University, K1S5B6, Ottawa, ON, Canada"
],
"type": "Organization"
},
"familyName": "Sack",
"givenName": "J\u00f6rg-R\u00fcdiger",
"id": "sg:person.01251275506.07",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01251275506.07"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/s00453-001-0027-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024365459",
"https://doi.org/10.1007/s00453-001-0027-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11902140_43",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009019781",
"https://doi.org/10.1007/11902140_43"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-52055-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1109702453",
"https://doi.org/10.1007/3-540-52055-4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4613-8369-7_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031111350",
"https://doi.org/10.1007/978-1-4613-8369-7_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187906",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039007193",
"https://doi.org/10.1007/bf02187906"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-003-1079-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012424731",
"https://doi.org/10.1007/s00453-003-1079-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00454-009-9204-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009856468",
"https://doi.org/10.1007/s00454-009-9204-0"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00454-003-2952-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036583060",
"https://doi.org/10.1007/s00454-003-2952-3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45678-3_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010056986",
"https://doi.org/10.1007/3-540-45678-3_15"
],
"type": "CreativeWork"
}
],
"datePublished": "2013-06-01",
"datePublishedReg": "2013-06-01",
"description": "We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain D\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal D$$\\end{document}, consisting of n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$n$$\\end{document} tetrahedra with positive weights, and a real number \u03b5\u2208(0,1)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varepsilon \\in (0,1)$$\\end{document}, our algorithm constructs paths in D\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal D$$\\end{document} from a fixed source vertex to all vertices of D\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal D$$\\end{document}, the costs of which are at most 1+\u03b5\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$1+\\varepsilon$$\\end{document} times the costs of (weighted) shortest paths, in O(C(D)n\u03b52.5logn\u03b5log31\u03b5)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(\\mathcal{C }(\\mathcal D )\\frac{n}{\\varepsilon ^{2.5}}\\log \\frac{n}{\\varepsilon }\\log ^3\\frac{1}{\\varepsilon })$$\\end{document} time, where C(D)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal{C }(\\mathcal D )$$\\end{document} is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25\u201353, 2005), to three dimensions.",
"genre": "article",
"id": "sg:pub.10.1007/s00454-013-9486-0",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1043660",
"issn": [
"0179-5376",
"1432-0444"
],
"name": "Discrete & Computational Geometry",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"approximation algorithm",
"shortest path",
"Shortest Path",
"algorithm",
"three-dimensional domain",
"source vertex",
"Voronoi diagram",
"geodesic paths",
"independent interest",
"path",
"real numbers",
"domain",
"positive weights",
"vertices",
"cost",
"local behavior",
"efficiency",
"depth study",
"polyhedral domains",
"aspect ratio",
"paper",
"ratio",
"interest",
"et al",
"number",
"time",
"geometric parameters",
"parameters",
"diagram",
"results",
"dimensions",
"behavior",
"weight",
"al",
"tetrahedra",
"study",
"Aleksandrov et al",
"Weighted 3-d Domains"
],
"name": "An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains",
"pagination": "124-184",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1018053658"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00454-013-9486-0"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00454-013-9486-0",
"https://app.dimensions.ai/details/publication/pub.1018053658"
],
"sdDataset": "articles",
"sdDatePublished": "2021-11-01T18:20",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_606.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00454-013-9486-0"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00454-013-9486-0'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00454-013-9486-0'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00454-013-9486-0'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00454-013-9486-0'

This table displays all metadata directly associated to this object as RDF triples.

160 TRIPLES      22 PREDICATES      73 URIs      56 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0801
3 schema:author Nf77b892475774fe9aac76eb6f3c5bd44
4 schema:citation sg:pub.10.1007/11902140_43
5 sg:pub.10.1007/3-540-45678-3_15
6 sg:pub.10.1007/3-540-52055-4
7 sg:pub.10.1007/978-1-4613-8369-7_3
8 sg:pub.10.1007/bf02187906
9 sg:pub.10.1007/s00453-001-0027-5
10 sg:pub.10.1007/s00453-003-1079-5
11 sg:pub.10.1007/s00454-003-2952-3
12 sg:pub.10.1007/s00454-009-9204-0
13 schema:datePublished 2013-06-01
14 schema:datePublishedReg 2013-06-01
15 schema:description We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal D$$\end{document}, consisting of n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} tetrahedra with positive weights, and a real number ε∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon \in (0,1)$$\end{document}, our algorithm constructs paths in D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal D$$\end{document} from a fixed source vertex to all vertices of D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal D$$\end{document}, the costs of which are at most 1+ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1+\varepsilon$$\end{document} times the costs of (weighted) shortest paths, in O(C(D)nε2.5lognεlog31ε)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$$\end{document} time, where C(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{C }(\mathcal D )$$\end{document} is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions.
16 schema:genre article
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N08bc69039ce9455bb1c28634e1367eb0
20 N0c8bf451b25f4039b01399e2216d31a2
21 sg:journal.1043660
22 schema:keywords Aleksandrov et al
23 Shortest Path
24 Voronoi diagram
25 Weighted 3-d Domains
27 al
28 algorithm
29 approximation algorithm
30 aspect ratio
31 behavior
32 cost
33 depth study
34 diagram
35 dimensions
36 domain
37 efficiency
38 et al
39 geodesic paths
40 geometric parameters
41 independent interest
42 interest
43 local behavior
44 number
45 paper
46 parameters
47 path
48 polyhedral domains
49 positive weights
50 ratio
51 real numbers
52 results
53 shortest path
54 source vertex
55 study
56 tetrahedra
57 three-dimensional domain
58 time
59 vertices
60 weight
61 schema:name An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains
62 schema:pagination 124-184
63 schema:productId Na5242c2042b24f5ea8d8aef5746c5220
64 Nd08b476a2a484609a7db3f8ba8bb6538
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018053658
66 https://doi.org/10.1007/s00454-013-9486-0
67 schema:sdDatePublished 2021-11-01T18:20
69 schema:sdPublisher N28227a3564064362a419342c9cee23a8
70 schema:url https://doi.org/10.1007/s00454-013-9486-0
72 sgo:sdDataset articles
73 rdf:type schema:ScholarlyArticle
75 rdf:rest N16a30f4838284c5299bd54fcc3dbe685
76 N08bc69039ce9455bb1c28634e1367eb0 schema:issueNumber 1
77 rdf:type schema:PublicationIssue
79 rdf:type schema:PublicationVolume
80 N16a30f4838284c5299bd54fcc3dbe685 rdf:first sg:person.012050257432.53
81 rdf:rest Na81bd8dabbef42e386006418a29a01f5
82 N28227a3564064362a419342c9cee23a8 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Na5242c2042b24f5ea8d8aef5746c5220 schema:name doi
85 schema:value 10.1007/s00454-013-9486-0
86 rdf:type schema:PropertyValue
87 Na81bd8dabbef42e386006418a29a01f5 rdf:first sg:person.01251275506.07
88 rdf:rest rdf:nil
89 Nd08b476a2a484609a7db3f8ba8bb6538 schema:name dimensions_id
90 schema:value pub.1018053658
91 rdf:type schema:PropertyValue
92 Nf77b892475774fe9aac76eb6f3c5bd44 rdf:first sg:person.012737765445.28
94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
95 schema:name Information and Computing Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
98 schema:name Artificial Intelligence and Image Processing
99 rdf:type schema:DefinedTerm
100 sg:journal.1043660 schema:issn 0179-5376
101 1432-0444
102 schema:name Discrete & Computational Geometry
103 schema:publisher Springer Nature
104 rdf:type schema:Periodical
105 sg:person.012050257432.53 schema:affiliation grid-institutes:grid.34428.39
106 schema:familyName Maheshwari
107 schema:givenName Anil
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012050257432.53
109 rdf:type schema:Person
110 sg:person.01251275506.07 schema:affiliation grid-institutes:grid.34428.39
111 schema:familyName Sack
112 schema:givenName Jörg-Rüdiger
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01251275506.07
114 rdf:type schema:Person
115 sg:person.012737765445.28 schema:affiliation grid-institutes:grid.424859.6
116 schema:familyName Aleksandrov
117 schema:givenName Lyudmil
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012737765445.28
119 rdf:type schema:Person
120 sg:person.014017262276.55 schema:affiliation grid-institutes:grid.148313.c
121 schema:familyName Djidjev
122 schema:givenName Hristo
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014017262276.55
124 rdf:type schema:Person
125 sg:pub.10.1007/11902140_43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009019781
126 https://doi.org/10.1007/11902140_43
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/3-540-45678-3_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010056986
129 https://doi.org/10.1007/3-540-45678-3_15
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/3-540-52055-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109702453
132 https://doi.org/10.1007/3-540-52055-4
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/978-1-4613-8369-7_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031111350
135 https://doi.org/10.1007/978-1-4613-8369-7_3
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/bf02187906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039007193
138 https://doi.org/10.1007/bf02187906
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/s00453-001-0027-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024365459
141 https://doi.org/10.1007/s00453-001-0027-5
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/s00453-003-1079-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012424731
144 https://doi.org/10.1007/s00453-003-1079-5
145 rdf:type schema:CreativeWork
146 sg:pub.10.1007/s00454-003-2952-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036583060
147 https://doi.org/10.1007/s00454-003-2952-3
148 rdf:type schema:CreativeWork
149 sg:pub.10.1007/s00454-009-9204-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009856468
150 https://doi.org/10.1007/s00454-009-9204-0
151 rdf:type schema:CreativeWork
152 grid-institutes:grid.148313.c schema:alternateName Los Alamos National Laboratory, 87545, Los Alamos, NM, USA
153 schema:name Los Alamos National Laboratory, 87545, Los Alamos, NM, USA
154 rdf:type schema:Organization
155 grid-institutes:grid.34428.39 schema:alternateName School of Computer Science, Carleton University, K1S5B6, Ottawa, ON, Canada
156 schema:name School of Computer Science, Carleton University, K1S5B6, Ottawa, ON, Canada
157 rdf:type schema:Organization
158 grid-institutes:grid.424859.6 schema:alternateName Bulgarian Academy of Sciences, IPP, Acad. G. Bonchev Str. Bl. 25-A, 1113, Sofia, Bulgaria
159 schema:name Bulgarian Academy of Sciences, IPP, Acad. G. Bonchev Str. Bl. 25-A, 1113, Sofia, Bulgaria
160 rdf:type schema:Organization