• Spanning ratio of shortest pat...

Treffer: Spanning ratio of shortest paths in weighted square tessellations

Title:
Spanning ratio of shortest paths in weighted square tessellations
Authors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Discrete, Combinational, and Computational Geometry, Bose, Prosenjit, Esteban Pascual, Guillermo, Orden Martin, David, Silveira, Rodrigo Ignacio
Publisher Information:
2022
Document Type:
E-Ressource Electronic Resource
Index Terms:
Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria algebraica, Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Geometry, Algebraic, Numerical analysis, Graph theory, Geometria algebraica, Anàlisi numèrica, Grafs, Teoria de, Classificació AMS::14 Algebraic geometry::14Q Computational aspects in algebraic geometry, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Classificació AMS::05 Combinatorics::05C Graph theory, Conference report
URL:
http://hdl.handle.net/2117/385087
https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdf
Availability:
Open access content. Open access content
Restricted access - publisher's policy
Note:
8 p.
application/pdf
English
Other Numbers:
HGF oai:upcommons.upc.edu:2117/385087
Bose, P. [et al.]. Spanning ratio of shortest paths in weighted square tessellations. A: European Workshop on Computational Geometry. "38th European Workshop on Computational Geometry (EuroCG 2022): Perugia, Italy: March 14-16, 2022: booklet of abstracts". 2022, p. 470-477.
1379091791
Contributing Source:
UNIV POLITECNICA DE CATALUNYA
From OAIster®, provided by the OCLC Cooperative.
Accession Number:
edsoai.on1379091791
Database:
OAIster

Weitere Informationen

Continuous 2-dimensional space is often discretized by considering a grid of weighted square cells. In this work we study how well a weighted tessellation approximates the space, with respect to shortest paths. In particular, we consider a shortest path SPw(s, t), which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path SGPw(s, t), which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio kSGPw(s,t)k kSPw(s,t)k is at most v 2 2+v 2 ˜ 1.08, irrespective of the weight assignment.
P. B. is partially supported by NSERC. G. E., D. O. and R. I. S. are partially supported by H2020-MSCA-RISE project 734922 - CONNECT and project PID2019-104129GB-I00 funded by MCIN/AEI/10.13039/501100011033. G. E. and D. O. are also supported by PIUAH21/IA-062 and CM/JIN/2021-004. G. E. is funded by an FPU of the Universidad de Alcalá.
Peer Reviewed
Postprint (author's final draft)