21 results for "Prosenjit Bose"
Showing 1–20 · 0.69 seconds · RSS
-
Journal Article
Formalization of the General Video Temporal Synchronization Problem
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…
-
Journal Article
Improved spanning ratio of the Theta-5 graph
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) }
-
Journal Article
Approximating the smallest $k$-enclosing geodesic disc in a simple polygon
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…
-
Journal Article
On the stretch factor of convex Delaunay graphs
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…
-
Journal Article
On Shortest Path, BFS- and DFS-Tree Graphs
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…
-
Journal Article
Expected complexity of routing in $\Theta_6$ and half-$\Theta_6$ graphs
…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…
-
Journal Article
Packing Plane Perfect Matchings into a Point Set
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…
-
Journal Article
Competitive local routing with constraints
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…
-
Journal Article
Routing on the visibility graph
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…
-
Journal Article
Local routing in WSPD-based spanners
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…
-
Journal Article
Optimal Algorithms for Separating a Polyhedron from its Single-Part Mold
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…
-
Journal Article
Separating layered treewidth and row treewidth
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…
-
Journal Article
Faster algorithms for some optimization problems on collinear points
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…
-
Journal Article
A plane 1.88-spanner for points in convex position
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…
-
Journal Article
Towards plane spanners of degree 3
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…
-
Journal Article
On the stretch factor of convex polyhedra whose vertices are (almost) on a sphere
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…
-
Journal Article
Network farthest-point diagrams
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…
-
Journal Article
On Separating Path and Tree Systems in Graphs
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…
-
Journal Article
Closest pair queries in vertical slabs and tight bounds on the number of possible answers
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…