Biblio Discovery — Demo Discovery Service

21 results for "Prosenjit Bose"

Showing 1–20 · 0.69 seconds · RSS

  1. Journal Article

    Formalization of the General Video Temporal Synchronization Problem

    Anthony Whitehead; Robert Laganiere; Prosenjit Bose

    ELCVIA Electronic Letters on Computer Vision and Image Analysis, Vol. 9 No. 1 · 2010 · English · DOAJ Scopus

    In this work, we present a theoretical formalization of the temporal synchronization problem and a method to temporally synchronize multiple stationary video cameras with overlapping views of the same scene. The method uses a two stage approach that first approximates the synchronization by…

  2. Journal Article

    Improved spanning ratio of the Theta-5 graph

    Prosenjit Bose; Darryl Hill; Aurélien Ooms

    Journal of Computational Geometry, Vol. 15 No. 1 · 2024 · English · DOAJ Scopus

    We show an upper bound of \( \frac{ \sin\left(\frac{3\pi}{10}\right) }{ \sin\left(\frac{2\pi}{5}\right)-\sin\left(\frac{3\pi}{10}\right) }

  3. Journal Article

    Approximating the smallest $k$-enclosing geodesic disc in a simple polygon

    Prosenjit Bose; Anthony D'Angelo; Stephane Durocher

    Journal of Computational Geometry, Vol. 16 No. 1 · 2025 · English · DOAJ Scopus

    We consider the problem of finding a geodesic disc of smallest radius containing at least $k$ points from a set of $n$ points in a simple polygon that has $m$ vertices, $r$ of which are reflex vertices. We refer to such a disc as a SKEG disc. We present an algorithm to compute a SKEG disc using…

  4. Journal Article

    On the stretch factor of convex Delaunay graphs

    Prosenjit Bose; Paz Carmi; Sebastien Collette et al.

    Journal of Computational Geometry, Vol. 1 No. 1 · 2010 · English · DOAJ Scopus

    Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DGC(S) of S is defined to be the dual of the Voronoi diagram of S with respect to the convex distance function defined by C. We prove that…

  5. Journal Article

    On Shortest Path, BFS- and DFS-Tree Graphs

    Prosenjit Bose; Amirali Madani; Anil Maheshwari et al.

    Journal of Graph Algorithms and Applications, Vol. 30 No. 1 · 2026 · English · DOAJ Scopus

    Flip graphs encode the structure of feasible transformations between combinatorial objects, making them a fundamental tool in reconfiguration problems. Tree graphs, which are flip graphs whose nodes represent the spanning trees of a graph, have received significant attention due to their…

  6. Journal Article

    Expected complexity of routing in $\Theta_6$ and half-$\Theta_6$ graphs

    Prosenjit Bose; Jean-Lou De Carufel; Olivier Devillers

    Journal of Computational Geometry, Vol. 11 No. 1 · 2020 · English · DOAJ Scopus

    …most $2\|st\|$ (resp. $2.89\|st\|$) which is optimal in the worst case [Bose et al, SIAM J. on Computing, 44(6)]. We propose alternative, slightly simpler routing algorithms that are optimal in the worst case and for which we provide an analysis of the average routing ratio for the $\Theta_6$-graph…

  7. Journal Article

    Packing Plane Perfect Matchings into a Point Set

    Ahmad Biniaz; Prosenjit Bose; Anil Maheshwari et al.

    Discrete Mathematics & Theoretical Computer Science, Vol. Vol. 17 no.2 No. Graph Theory · 2015 · English · DOAJ Scopus

    Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of ⌊log2$n$⌋$-1$. For some special configurations of point sets, we give the exact…

  8. Journal Article

    Competitive local routing with constraints

    Prosenjit Bose; Rolf Fagerberg; André van Renssen et al.

    Journal of Computational Geometry, Vol. 8 No. 1 · 2017 · English · DOAJ Scopus

    Let $P$ be a set of $n$ vertices in the plane and $S$ a set of non-crossing line segments between vertices in $P$, called constraints. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained $\Theta_m$-graph is constructed…

  9. Journal Article

    Routing on the visibility graph

    Prosenjit Bose; Matias Korman; Sander Verdonschot et al.

    Journal of Computational Geometry, Vol. 9 No. 1 · 2018 · English · DOAJ Scopus

    We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two…

  10. Journal Article

    Local routing in WSPD-based spanners

    Jean-Lou De Carufel; Prosenjit Bose; Frédérik Paradis et al.

    Journal of Computational Geometry, Vol. 12 No. 1 · 2021 · English · DOAJ Scopus

    The well-separated pair decomposition (WSPD) of the complete Euclidean graph defined on points in $R^2$, introduced by Callahan and Kosaraju [JACM, 42 (1): 67-90, 1995], is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many…

  11. Journal Article

    Optimal Algorithms for Separating a Polyhedron from its Single-Part Mold

    Prosenjit Bose; Efi Fogel; Tzvika Geft et al.

    Computing in Geometry and Topology, Vol. 3 No. 1 · 2024 · English · DOAJ

    Casting is a manufacturing process where liquid material is poured into a mold having the shape of a desired product. After the material solidifies, the product is removed from the mold. We study the case where the mold is made of a single part and the object to be produced is a three-dimensional…

  12. Journal Article

    Separating layered treewidth and row treewidth

    Prosenjit Bose; Vida Dujmović; Mehrnoosh Javarsineh et al.

    Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no. 1, Iss Graph Theory… · 2022 · English · DOAJ Scopus

    Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. It follows from the definitions that the layered treewidth of a graph is at most its row treewidth plus 1. Moreover, a minor-closed class…

  13. Journal Article

    Faster algorithms for some optimization problems on collinear points

    Ahmad Biniaz; Prosenjit Bose; Paz Carmi et al.

    Journal of Computational Geometry, Vol. 11 No. 1 · 2020 · English · DOAJ Scopus

    We propose faster algorithms for the following three optimization problems on $n$ collinear points, i.e., points in dimension one. The first two problems are known to be NP-hard in higher dimensions. 1- Maximizing total area of disjoint disks: In this problem the goal is to maximize the total area…

  14. Journal Article

    Coloring and Guarding Arrangements

    Prosenjit Bose; Jean Cardinal; Sébastien Collette et al.

    Discrete Mathematics & Theoretical Computer Science, Vol. Vol. 15 no. 3 No. Combinatorics · 2013 · English · DOAJ Scopus

    Combinatorics

  15. Journal Article

    A plane 1.88-spanner for points in convex position

    Ahmad Biniaz; Mahdi Amani; Anil Maheshwari et al.

    Journal of Computational Geometry, Vol. 7 No. 1 · 2016 · English · DOAJ Scopus

    Let $S$ be a set of $n$ points in the plane that is in convex position. For a real number $t>1$, we say that a point $p$ in $S$ is $t$-good if for every point $q$ of $S$, the shortest-path distance between $p$ and $q$ along the boundary of the convex hull of $S$ is at most $t$ times the Euclidean…

  16. Journal Article

    Towards plane spanners of degree 3

    Ahmad Biniaz; Prosenjit Bose; Jean-Lou De Carufel et al.

    Journal of Computational Geometry, Vol. 8 No. 1 · 2017 · English · DOAJ Scopus

    Let $S$ be a finite set of points in the plane. In this paper we consider the problem of computing plane spanners of degree at most three for $S$. • If $S$ is in convex position, then we present an algorithm that constructs a plane $\frac{3+4\pi}{3}$-spanner for $S$ whose vertex degree is at most…

  17. Journal Article

    On the stretch factor of convex polyhedra whose vertices are (almost) on a sphere

    Michiel Smid; Prosenjit Bose; Paz Carmi et al.

    Journal of Computational Geometry, Vol. 7 No. 1 · 2016 · English · DOAJ Scopus

    Let $P$ be a convex polyhedron in $\mathbb{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 vertices are on the unit-sphere, the skeleton is a $(0.999 \cdot \pi)$-spanner. If the vertices are very close to this…

  18. Journal Article

    Network farthest-point diagrams

    Prosenjit Bose; Kai Dannies; Jean-Lou De Carufel et al.

    Journal of Computational Geometry, Vol. 4 No. 1 · 2013 · English · DOAJ Scopus

    Consider the continuum of points along the edges of a network, i.e., an undirected graph with positive edge weights. We measure distance between these points in terms of the shortest path distance along the network, known as the network distance. Within this metric space, we study farthest…

  19. Journal Article

    On Separating Path and Tree Systems in Graphs

    Ahmad Biniaz; Prosenjit Bose; Jean-Lou De Carufel et al.

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 27:2 No. Graph Theory · 2025 · English · DOAJ Scopus

    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 elements in $X$, there exists a set in the separating system that contains exactly one of the two elements. A separating…

  20. Journal Article

    Closest pair queries in vertical slabs and tight bounds on the number of possible answers

    Ahmad Biniaz; Prosenjit Bose; Chaeyoon Chung et al.

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · English · DOAJ Scopus

    Let $S$ be a set of $n$ points in $\mathbb{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 first coordinates, such that exactly $n/m$ points of $S$ are between any two successive hyperplanes. Let $A(S,m)$ be the…