descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object , Part of book or chapter of book 01 Jan 2023Embargo end date: 01 Jan 2023Publisher:arXiv

Authors: Löffler, M.; Ophelders, Tim; Silveira, Rodrigo Ignacio; Staals, Frank;

doi: 10.48550/arxiv.2303.08937

arXiv: http://arxiv.org/abs/2303.08937

handle: 2117/403858 , 2117/428421

Shortest Paths in Portalgons

- Summary
- Subjects
- Metrics

Abstract

Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.

Tim Ophelders: Partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Rodrigo I. Silveira: Partially funded by MICINN through project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033.

Peer Reviewed

Related Organizations

Universitat Politècnica de Catalunya
Spain
Utrecht University
Netherlands
Leibniz Association
Germany
Universitat Polite`cnica de Catalunya
Spain
Schloss Dagstuhl – Leibniz Center for Informatics
Germany

View all View all

Keywords

Computational Geometry (cs.CG), FOS: Computer and information sciences, Shortest paths, Classificació AMS::05 Combinatorics::05C Graph theory, Delaunay triangulation, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Number theory, Computer Science - Data Structures and Algorithms, Classificació AMS::11 Number theory::11Y Computational number theory, Data Structures and Algorithms (cs.DS), geodesic distance, Anàlisi numèrica, shortest paths, Geodesic distance, Grafs, Teoria de, Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica, Nombres, Teoria dels, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, 004, Graph theory, Polyhedral surfaces, Computer Science - Computational Geometry, Àrees temàtiques de la UPC::Matemàtiques i estadística::Àlgebra::Teoria de nombres, Software, Numerical analysis, ddc: ddc:004

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average