Prosenjit Bose

activity

20242026

collaborators

11 papers

cs.CG2026

On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets

Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari +3

The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an ear…

cs.DM2026

3-packings in Triangulations: Algorithms, bounds, and Complexity

Prosenjit Bose, Anil Maheshwari, Bobby Miraftab +1

We study $H$ -packings in plane triangulations for the three-vertex graphs $H \in {P_{3}, K_{3}, P_{2} \cup P_{1}}$ . For a graph $H$ , let $I^»_{H} (G)$ denote the maximum size of an $H$ -packing in…

cs.CG2026

Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6

Let $S$ be a set of $n$ points in $R^{d}$ , where $d \geq 2$ is a constant, and let $H_{1}, H_{2}, \dots, H_{m + 1}$ be a sequence of vertical hyperplanes that are sorted by their fi…

cs.CG2026

On geodesic disks enclosing many points

Prosenjit Bose, Guillermo Esteban, David Orden +2

Let $I^(n)$ be the largest number such that for every set $S$ of $n$ points in a polygon~ $P$ , there always exist two points $x, y \in S$ , where every geodesic disk contai…

math.CO2026

Cops and robber in graphs with bounded vertex cover number

Prosenjit Bose, Louis Esperet, JÄdrzej Hodor +3

Meyniel's conjecture states that $n$ -vertex connected graphs have cop number $O (n)$ . The current best known upper bound is $n / 2^{(1 - o (1)) l o g n}$ , proved independentl…

cs.CG2026

Computational aspects of disks enclosing many points

Prosenjit Bose, Guillermo Esteban, Tyler Tuttle

Let $S$ be a set of $n$ points in the plane. We present several different algorithms for finding a pair of points in $S$ such that any disk that contains that pair must contain at…