Publications (122)
Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
Nicolas Bonichon, Prosenjit Bose, Paz Carmi +3
A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is - and -monotone. Angle-monotone graphs are -spa…
Towards a General Framework for Searching on a Line and Searching on Rays
Prosenjit Bose, Jean-Lou De Carufel
Consider the following classical search problem: given a target point , starting at the origin, find with minimum cost, where cost is defined as the distance travelle…
Continuous Yao Graphs
Luis Barba, Prosenjit Bose, Jean-Lou De Carufel +5
In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points and an angle , we define the continuous Yao gr…
On the stretch factor of the Theta-4 graph
Luis Barba, Prosenjit Bose, Jean-Lou De Carufel +2
In this paper we show that the θ-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constan…
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…
Geometric Spanners With Small Chromatic Number
Prosenjit Bose, Paz Carmi, Mathieu Couture +3
Given an integer , we consider the problem of computing the smallest real number such that for each set of points in the plane, there exists a -spanner f…