P. Bose

activity

20052023

most citedOn the stretch factor of the Theta-4 graph

8 citations · 31 across the 23 of their papers we have counts for

collaborators

Showing 2019Show all

3 papers · 1 filter

cs.CG2019★ 1 cited

Expected Complexity of Routing in $Θ$ 6 and Half- $Θ$ 6 Graphs

Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers

We study online routing algorithms on the $Θ$ 6-graph and the half- $Θ$ 6-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target…

cs.DS2019

Competitive Online Search Trees on Trees

Prosenjit Bose, Jean Cardinal, John Iacono +2

We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tre…

cs.CG2019

Near-Optimal $O (k)$ -Robust Geometric Spanners

Prosenjit Bose, Paz Carmi, Vida Dujmovic +1

For any constants $d \geq 1$ , $ε > 0$ , $t > 1$ , and any $n$ -point set $P \subset R^{d}$ , we show that there is a geometric graph $G = (P, E)$ having $O (n lo g^{2} n lo g lo g n)$ edges with…

Expected Complexity of Routing in Θ 6 and Half-Θ 6 Graphs

Competitive Online Search Trees on Trees

Near-Optimal O(k)-Robust Geometric Spanners

Expected Complexity of Routing in $Θ$ 6 and Half- $Θ$ 6 Graphs

Near-Optimal $O (k)$ -Robust Geometric Spanners