A divide-and-conquer based preprocessing for routing in a simple polygon

Siddharth Gaur () and R. Inkulu ()
Additional contact information
Siddharth Gaur: Indian Institute of Technology Guwahati
R. Inkulu: Indian Institute of Technology Guwahati

Journal of Combinatorial Optimization, 2025, vol. 50, issue 2, No 6, 18 pages

Abstract: Abstract Given a simple polygon P defined with n vertices in the plane, we preprocess P and compute routing tables at every vertex of P. In the routing phase, a packet originating at any source vertex of P is routed to its destination vertex belonging to P. At every vertex v of P along the routing path, until the packet reaches its destination, the next hop is determined using the routing tables at v and the additional information (including the packet’s destination vertex label) in the packet. We show our routing scheme constructs routing tables in $$O\big (n \big (1+\frac{1}{\epsilon }\big ) \big (\lg {n}\big )^3\big )$$ time and the routing tables at all the vertices of P together use $$O\big (n+\frac{n}{\epsilon }\big (\lg {n}\big )^3\big )$$ space. The multiplicative stretch factor of the routing path computed by our algorithm is upper bounded by $$(2+\epsilon )\lg {n}$$ . Here, $$\epsilon > 0$$ is an input parameter.

Keywords: Computational geometry; Geometric shortest paths; Geometric routing; Approximation algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01345-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:2:d:10.1007_s10878-025-01345-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01345-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().