J. De Carufel

activity

20102026

most citedRevisiting the Problem of Searching on a Line

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

collaborators

29 papers

cs.DS2026

Minimum Sum Vertex Cover via Minimum Vertex Cover

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +2

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.…

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.CG2025

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.CG2024

Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +1

Let $H$ be an edge-weighted graph, and let $G$ be a subgraph of $H$ . We say that $G$ is an $f$ -fault-tolerant $t$ -spanner for $H$ , if the following is true for any subset $F$ of at…

math.CO2024

So Long Sucker: Endgame Analysis

Jean-Lou De Carufel, Marie Rose Jerade

So Long Sucker is a strategy board game that requires 4 players, each with $c$ chips of their designated color, and a board made of $k$ empty piles. With a clear set-up comes intri…

cs.CG2023

The Exact Spanning Ratio of the Parallelogram Delaunay Graph

Prosenjit Bose, Jean-Lou De Carufel, Sandrine Njoo

Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which…

cs.DM2023★ 1 cited

On Separating Path and Tree Systems in Graphs

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel +6

We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct element…

math.CO2023★ 2 cited

Cop numbers of periodic graphs

Jean-Lou De Carufel, Paola Flocchini, Nicola Santoro +1

A \emph{periodic graph} $G = (G_{0}, G_{1}, G_{2}, \dots)$ with period $p$ is an infinite periodic sequence of graphs $G_{i} = G_{i + p} = (V, E_{i})$ , where $i \geq 0$ . The graph $G=(V,…

cs.CG2018

Convex Polygons in Cartesian Products

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans +4

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of $n$ real numbers (for short, \emph{grid}). First, we prove that every…

cs.CG2018

On the Spanning and Routing Ratio of Directed Theta-Four

Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill +1

We present a routing algorithm for the directed $Θ_{4}$ -graph, here denoted as the $\overrightarrow{Θ_4}}$-graph, that computes a path between any two vertices $s$ and $t$ having len…

cs.CG2018

Reconstructing a convex polygon from its $ω$ -cloud

Elena Arseneva, Prosenjit Bose, Jean-Lou De Carufel +1

An $ω$ -wedge is the closed set of points contained between two rays that are emanating from a single point (the apex), and are separated by an angle $ω < π$ . Given a convex polygon…

cs.CG2017

Optimal Art Gallery Localization is NP-hard

Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet +1

Art Gallery Localization (AGL) is the problem of placing a set $T$ of broadcast towers in a simple polygon $P$ in order for a point to locate itself in the interior. For any point…

cs.CG2017★ 3 cited

Art Gallery Localization

Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet +1

We study the problem of placing a set $T$ of broadcast towers in a simple polygon $P$ in order for any point to locate itself in the interior of $P$ . Let $V (p)$ denote the visibili…

cs.CG2016

Minimizing the Continuous Diameter when Augmenting a Geometric Tree with a Shortcut

Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari +2

We augment a tree $T$ with a shortcut $pq$ to minimize the largest distance between any two points along the resulting augmented tree $T + pq$ . We study this problem in a continuous…

cs.CG2016★ 5 cited

Towards Plane Spanners of Degree 3

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel +3

Let $S$ be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane $\frac{3 + 4 π}{3}$ -spanner of $S$ whose vertex degree is a…

cs.CG2016

Constrained Generalized Delaunay Graphs Are Plane Spanners

Prosenjit Bose, Jean-Lou De Carufel, André van Renssen

We look at generalized Delaunay graphs in the constrained setting by introducing line segments which the edges of the graph are not allowed to cross. Given an arbitrary convex shap…

cs.CG2015

Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts

Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari +1

We seek to augment a geometric network in the Euclidean plane with shortcuts to minimize its continuous diameter, i.e., the largest network distance between any two points on the a…

cs.CG2015★ 1 cited

On the Stretch Factor of Convex Polyhedra whose Vertices are (Almost) on a Sphere

Prosenjit Bose, Paz Carmi, Mirela Damian +5

Let $P$ be a convex polyhedron in $R^{3}$ . The skeleton of $P$ is the graph whose vertices and edges are the vertices and edges of $P$ , respectively. We prove that, if these…

cs.CG2015★ 1 cited

On interference among moving sensors and related problems

Jean-Lou De Carufel, Matya Katz, Matias Korman +3

We show that for any set of $n$ points moving along "simple" trajectories (i.e., each coordinate is described with a polynomial of bounded degree) in $ℜ^{d}$ and any parameter $2 \…

cs.CG2015★ 3 cited

Probing Convex Polygons with a Wedge

Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet +1

Minimizing the number of probes is one of the main challenges in reconstructing geometric objects with probing devices. In this paper, we investigate the problem of using an $ω$ -we…

cs.CG2015

Discrete Voronoi Games and $ε$ -Nets, in Two and Three Dimensions

Aritra Banik, Jean-Lou De Carufel, Anil Maheshwari +1

The one-round discrete Voronoi game, with respect to a $n$ -point user set $U$ , consists of two players Player 1 ( $P_{1}$ ) and Player 2 ( $P_{2}$ ). At first, $\mathca…

cs.CG2015★ 4 cited

A linear-time algorithm for the geodesic center of a simple polygon

Hee-Kap Ahn, Luis Barba, Prosenjit Bose +3

Given two points in a simple polygon $P$ of $n$ vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within $P$ . The geod…

cs.CG2014★ 1 cited

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 $S \subset R^{2}$ and an angle $0 < θ \leq 2 π$ , we define the continuous Yao grap…

cs.DS2014

Towards a General Framework for Searching on a Line and Searching on $m$ Rays

Prosenjit Bose, Jean-Lou De Carufel

Consider the following classical search problem: given a target point $p \in ℜ$ , starting at the origin, find $p$ with minimum cost, where cost is defined as the distance travelle…

Minimum Sum Vertex Cover via Minimum Vertex Cover

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

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

Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults

So Long Sucker: Endgame Analysis

The Exact Spanning Ratio of the Parallelogram Delaunay Graph

On Separating Path and Tree Systems in Graphs

Cop numbers of periodic graphs

Convex Polygons in Cartesian Products

On the Spanning and Routing Ratio of Directed Theta-Four

Reconstructing a convex polygon from its ω-cloud

Optimal Art Gallery Localization is NP-hard

Art Gallery Localization

Minimizing the Continuous Diameter when Augmenting a Geometric Tree with a Shortcut

Towards Plane Spanners of Degree 3

Constrained Generalized Delaunay Graphs Are Plane Spanners

Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts

On the Stretch Factor of Convex Polyhedra whose Vertices are (Almost) on a Sphere

On interference among moving sensors and related problems

Probing Convex Polygons with a Wedge

Discrete Voronoi Games and ε-Nets, in Two and Three Dimensions

A linear-time algorithm for the geodesic center of a simple polygon

Continuous Yao Graphs

Towards a General Framework for Searching on a Line and Searching on m Rays

Reconstructing a convex polygon from its $ω$ -cloud

Discrete Voronoi Games and $ε$ -Nets, in Two and Three Dimensions

Towards a General Framework for Searching on a Line and Searching on $m$ Rays