An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2013-06-01

AUTHORS

Lyudmil Aleksandrov, Hristo Djidjev, Anil Maheshwari, Jörg-Rüdiger Sack

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
  • 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: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "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", 
            "volumeNumber": "50"
          }
        ], 
        "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", 
          "additive Voronoi diagrams", 
          "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    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'

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s00454-013-9486-0 schema:about anzsrc-for:08
    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
    26 additive Voronoi diagrams
    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
    68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    69 schema:sdPublisher N28227a3564064362a419342c9cee23a8
    70 schema:url https://doi.org/10.1007/s00454-013-9486-0
    71 sgo:license sg:explorer/license/
    72 sgo:sdDataset articles
    73 rdf:type schema:ScholarlyArticle
    74 N000651018af94a45adac09119e375680 rdf:first sg:person.014017262276.55
    75 rdf:rest N16a30f4838284c5299bd54fcc3dbe685
    76 N08bc69039ce9455bb1c28634e1367eb0 schema:issueNumber 1
    77 rdf:type schema:PublicationIssue
    78 N0c8bf451b25f4039b01399e2216d31a2 schema:volumeNumber 50
    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
    93 rdf:rest N000651018af94a45adac09119e375680
    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
     




    Preview window. Press ESC to close (or click here)


    ...