Abstract Rotationally Monotone Polygons ∗ (2009)
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A generalization of monotonicity is introduced. An nvertex polygon P is rotationally monotone w.r.t. a point r if there exists a partitioning of the boundary of P into exactly two polygonal chains,...
www.cs.uu.nl Area-Preserving Approximations of Polygonal Paths ∗† (2009)
Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Van Kreveld, Bettina Speckmann, Prosenjit Bose, ...
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Every Large Point Set contains Many Collinear Points or an Empty Pentagon (2009)
Abel, Zachary, Ballinger, Brad, Bose, Prosenjit, Collette, Sébastien, Dujmović, Vida, Hurtado, Ferran, ...
We prove the following generalised empty pentagon theorem: for every integer $\ell \geq 2$, every sufficiently large set of points in the plane contains $\ell$ collinear points or an empty pentagon....
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2009)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
Algorithms for Packing Two Circles in a Convex Polygon (2009)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Anil Maheshwari
3
Algorithms for Designing Clamshell Molds (2008)
Stefanie Wuhrer, Prosenjit Bose, Pat Morin, Michiel Smid
Clamshell casting is a popular manufacturing technique where liquid is poured into a mold or cast and the cast is removed once the liquid has hardened. The term clamshell refers to the way in which...
Efficient Algorithms for Petersen's Matching Theorem (2008)
Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw
Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding...
On the stabbing number of a random Delaunay triangulation (2008)
We consider a Delaunay triangulation defined on n points distributed independently and uniformly on a planar compact convex set of positive volume. Let the stabbing number be the maximal number of...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2008)
Prosenjit Bose, Danny Krizanc, Stefan Langerman, Pat Morin
Abstract A graph G is a 2-tree if G = K3, or G has a vertex vof degree 2, whose neighbours are adjacent, and G \ vis a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
Vertex Pops and Popturns (2008)
Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine
This paper considers transformations of a planar polygon P according to two types of operations. A vertex pop (or a pop) reflects a vertex vi, i ∈ {1,..., n}, across the line through the two...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
A Linear-Space Algorithm for Distance Preserving Graph Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in d-dimensional Euclidean space for a constant d so that for each edge the distance between...
Communication-Efficient Construction of the Plane Localized Delaunay Graph (2008)
Bose, Prosenjit, Carmi, Paz, Smid, Michiel, Xu, Daming
Let $V$ be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane $\frac{4 \pi \sqrt{3}}{9}$-spanner of the unit-disk graph $\UDG(V)$. This algorithm makes only...
Induced Subgraphs of Bounded Degree and Bounded Treewidth ⋆ (2008)
Prosenjit Bose, Vida Dujmović, David R. Wood
Abstract. We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a ‘large ’ induced subgraph H, where H has treewidth at most t and every vertex in H has...
Succinct Data Structures for Approximating Convex Functions with Applications ⋆ (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ɛ-approximations of convex functions whose slopes are bounded. Since the queries are efficient in these structures requiring only O(log(1/ε)+log log...
Succinct Geometric Indexes Supporting Point Location Queries (2008)
Bose, Prosenjit, Chen, Eric Y., He, Meng, Maheshwari, Anil, Morin, Pat
We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that, by taking advantage of the n points in the data set permuted and stored...
Morphing of Triangular Meshes in Shape Space (2008)
Wuhrer, Stefanie, Bose, Prosenjit, Shu, Chang, O'Rourke, Joseph, Brunton, Alan
We present a novel approach to morph between two isometric poses of the same non-rigid object given as triangular meshes. We model the morphs as linear interpolations in a suitable shape space...
On the Stretch Factor of Convex Delaunay Graphs (2008)
Bose, Prosenjit, Carmi, Paz, Collette, Sebastien, Smid, Michiel
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 DG_C(S) of S is defined to be the dual of...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2008)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
On Structural and Graph Theoretic Properties of Higher Order Delaunay Graphs ∗ (2008)
Manuel Abellanas, Prosenjit Bose, Jesús García, Ferran Hurtado
Given a set P of n points in the plane, the order-k Delaunay graph is a graph with vertex set P and an edge exists between two points p, q ∈ P when there is a circle through p and q with at most k...
Abstract On Computing Enclosing Isosceles Triangles and Related Problems (2008)
Prosenjit Bose, Carlos Seara, Saurabh Sethia
Given a set of n points in the plane, we show how to compute various enclosing isosceles triangles where different parameters such as area or perimeter are optimized. We then study a 3-dimensional...
Abstract On Properties of Higher Order Delaunay Graphs with Applications ∗ (2008)
Manuel Abellanas, Prosenjit Bose, Jesús García, Ferran Hurtado, Mariano Nicolás, Pedro A. Ramos
In this work we study the order-k Delaunay graph, which is formed by edges pq having a circle through p and q and containing no more than k sites. We study the combinatorial structure of the set of...
TRECVID 2006 NOTEBOOK PAPER: FEATURE BASED CUT DETECTION WITH AUTOMATIC THRESHOLD SELECTION (2008)
Anthony Whitehead, Prosenjit Bose, Robert Laganière
Our approach is based on feature tracking where cuts are detected when only few features can be tracked across frame pairs. This unique criterion was found sufficient to detect most cuts in most...
Abstract Dynamic Optimality for Skip Lists and B-Trees (2008)
Prosenjit Bose, Karim Douïeb, Stefan Langerman
Sleator and Tarjan [39] conjectured that splay trees are dynamically optimal binary search trees (BST). In this context, we study the skip list data structure introduced by Pugh [35]. We prove that...
CONNECTIVITY–PRESERVING TRANSFORMATIONS OF BINARY IMAGES (2008)
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Pat Morin
ABSTRACT. A binary image I is Ba, Wb-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a Ba, Wb-connected image...
Abstract Routing with Guaranteed Delivery in ad hoc Wireless Networks* (2008)
Prosenjit Bose, Pat Morin, Jorge Urrutia
We consider routing problems in ad hoc wireless net-works modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the dis-tance between them is less than some...
ALGORITHMS FOR OPTIMAL OUTLIER REMOVAL ∗ (2008)
Rossen Atanassov, Prosenjit Bose, Mathieu Couture, Anil Maheshwari, Pat Morin, Michel Paquette, ...
Abstract. We consider the problem of removing c points from a set S of n points so that the remaining point set is optimal in some sense. Definitions of optimality we consider include having minimum...
CONNECTIVITY–PRESERVING TRANSFORMATIONS OF BINARY IMAGES (2008)
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Pat Morin
ABSTRACT. A binary image I is Ba, Wb-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a Ba, Wb-connected image...
On Generalized Diamond Spanners (2008)
Prosenjit Bose, Aaron Lee, Michiel Smid
Given a set P of points in the plane and a set L of non-crossing line segments whose endpoints are in P, a constrained plane geometric graph is a plane graph whose vertex set is P and whose edge set...
Computing the Tool Path of an Externally Monotone Polygon in Linear Time ∗ (2008)
Prosenjit Bose, David Bremner, Diane Souvaine
A Numerically-Controlled (NC) machine typically consists of a worktable and a spindle (or cutter) with several axes of freedom for positioning the tool. In this paper,
Vertex Pops and Popturns (2008)
Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine
This paper considers transformations of a planar polygon P according to two types of operations. A vertex pop (or a pop) reflects a vertex vi, i ∈ {1,..., n}, across the line through the two...
On the falsepositive rate of Bloom filters (2008)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
www.cs.uu.nl Area-Preserving Approximations of Polygonal Paths ∗† (2008)
Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Van Kreveld, Bettina Speckmann, Prosenjit Bose, ...
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [9]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Experimental Results on Quadrangulations of Sets of Fixed Points (2008)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining “nice ” quadrangulations of planar sets of points. For many applications “nice ” means that the quadrilaterals obtained are convex if possible and as...
Experimental Results on Quadrangulations of Sets of Fixed Points (2008)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
SUCCINCT DATA STRUCTURES FOR APPROXIMATING CONVEX FUNCTIONS, WITH APPLICATIONS † (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ε-approximations of convex functions whose slopes are bounded from above and below by n and −n, respectively. The structures we describe have size...
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed by a rotation once the liquid has hardened. We consider the case where the object to...
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [11]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P, a flipturn involves reflecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grünbaum (1995)) showed that any polygon on n vertices...
Testing the Quality of Manufactured Disks and Balls ∗ (2008)
We consider the problem of testing the roundness of manufactured disks and balls using the finger probing model of Cole and Yap [6]. The running time of our procedures depends on the quality of the...
Coarse Grained Parallel Algorithms For Graph Matching ∗ (2008)
Albert Chan, Frank Dehne, Prosenjit Bose, Markus Latzel
Parallel graph algorithm design is a very well studied topic. Many results have been presented for the PRAM model. However, these algorithms are inherently fine grained and experiments show that PRAM...
vol., no., pp. – () The Maximum Number of Edges in a Three-Dimensional Grid-Drawing ∗ (2008)
Prosenjit Bose, Jurek Czyzowicz, Gatineau Québec Canada, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bound-ing box. The first universal lower bound on the volume of...
SUCCINCT DATA STRUCTURES FOR APPROXIMATING CONVEX FUNCTIONS, WITH APPLICATIONS † (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ε-approximations of convex functions whose slopes are bounded from above and below by n and −n, respectively. The structures we describe have size...
Succinct Data Structures for Approximating Convex Functions with Applications ⋆ (2008)
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing ɛ-approximations of convex functions whose slopes are bounded. Since the queries are efficient in these structures requiring only O(log(1/ε)+log log...
Spanners of Additively Weighted Point Sets (2008)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu
We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs $(p,r)$ where $p$ is a point in the plane and $r$ is a real number....
Spanners of Complete $k$-Partite Geometric Graphs (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Morin, Pat, Smid, Michiel
We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\mathbb{R}^d$, compute a spanner of $K$ that has a ``small'' stretch...
Cutting Rectangles in Equal Area Pieces (2007)
Prosenjit Bose, Jurek Czyzowicz, Dominic Lessard
this paper we restrict our attention to straight line orthogonal cuts. We assume that each cut is complete in that it divides a rectangle into two pieces.
Experimental Results on Quadrangulations of Sets of Points (2007)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining "nice" quadrangulations of planar sets of points. For many applications "nice" means that the quadrilaterals obtained are convex if possible...
Fast Approximation of Sums of Distances (2007)
Prosenjit Bose, Anil Maheshwari, Pat Morin
We show how to preprocess a set S of n points in R d (d constant) using O(kn log d 1 n) time and space so that the sum of distances of points in S to a query point q can be approximated to within a...
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing #-approximations of convex functions whose slopes are bounded. Since the queries are e#cient in these structures requiring only O(log(1/#)+log log n)...
On the falsepositive rate of Bloom filters (2007)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
Prosenjit Bose, Evangelos Kranakis, Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r0, r0...
Prosenjit Bose, Godfried Toussaint
Abstract--- In the manufacturing industry, finding a suitable location for the pin gate (the pin gate is the point from which liquid is poured or injected into a mold) is a difficult problem when...
Geometric and Computational Aspects of Injection (2007)
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after the injection process is an important and difficult problem which...
Every set of disjoint line segments admits a binary tree, Discrete Comput Geom (2007)
Prosenjit Bose, Michael E. Houle, Godfried Toussaint
Given a set of n disjoint line segments in the plane, we show that it is always possible to form a tree with the endpoints of the segments such that each line segment is an edge of the tree, the tree...
Prosenjit Bose, Pat Morin, Jorge Urrutia
We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some xed...
On Local Transformations in Plane GeometricGraphs Embedded on Small Grids (Extended Abstract) (2007)
Extended Abstract, Prosenjit Bose, Manuel Abellanas, Alfredo Garcia, Pedro Ramos, Ferran Hurtado, ...
Manuel Abellanas , Prosenjit Bose , Alfredo Garca , Ferran Hurtado , Pedro Ramos , Eduardo Rivera-Campo , and Javier Tejel Facultad de Informatica, U. Politecnica de Madrid, Madrid, Spain School of...
Prosenjit Bose, Joachim Gudmundsson, Pat Morin
Let V be a set of n points in R . The -graph of V is a geometric graph with vertex set V that has been studied extensively and which has several nice properties. We introduce a new variant of -graphs...
Some Aperture-Angle Optimization Problems (2007)
Prosenjit Bose, Ferran Hurtado-Diaz, Elsa Omana-Pulido, Jack Snoeyink, Godfried T. Toussaint
Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P, the aperture angle of x with respect to Q is defined as the angle of the cone that:...
Approximating Geometric Bottleneck Shortest Paths (2007)
Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
Testing the Quality of Manufactured Disks and Balls (2007)
We consider the problem of testing the roundness of manufactured disks and balls using the finger probing model of Cole and Yap [6]. The running time of our procedures depends on the quality of the...
Prosenjit Bose, Luc Devroye, Pat Morin
Abstract. We study data structures for providing #-approximations of convex functions whose slopes are bounded. Since the queries are e#cient in these structures requiring only O(log(1/#)+log log n)...
Geodesic Ham-Sandwich Cuts (2007)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, ...
Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m+r+b. A ham-sandwich geodesic is a shortest path in P...
Packing Two Disks into a Polygonal Environment (2007)
We consider the following problem. Given a polygon P , possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P , and...
Geometric Spanners With Small Chromatic Number (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Smid, Michiel, Zeh, Norbert
Given an integer $k \geq 2$, we consider the problem of computing the smallest real number $t(k)$ such that for each set $P$ of points in the plane, there exists a $t(k)$-spanner for $P$ that has...
A polynomial bound for untangling geometric planar graphs (2007)
Bose, Prosenjit, Dujmovic, Vida, Hurtado, Ferran, Langerman, Stefan, Morin, Pat, Wood, David R.
To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos [Discrete Comput. Geom., 2002] asked if every n-vertex...
On a family of strong geometric spanners that admit local routing strategies (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Smid, Michiel, Xu, Daming
We introduce a family of directed geometric graphs, denoted $\paz$, that depend on two parameters $\lambda$ and $\theta$. For $0\leq \theta
Geometric spanners with small chromatic number (2007)
Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel Smid, Norbert Zeh
Abstract. Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)-spanner for P that has...
A polynomial bound for untangling geometric planar graphs (2007)
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Stefan Langerman, Pat Morin, David R. Wood
ABSTRACT. To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos [Discrete Comput. Geom., 2002] asked if every...
Axis-aligned traversals of points with a minimum number of turns (2007)
Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, Pavel Valtr
Abstract Given a finite set of points S in Rd, consider visiting the points in S with a polygonal path whichmakes a minimum number of turns, or equivalently, has the the minimum number of segments...
Rotationally Monotone Polygons, Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
doi:10.1016/j.comgeo.2007.02.004 www.elsevier.com/locate/comgeo We introduce a generalization of monotonicity. An n-vertex polygon P is rotationally monotone with respect to a point r if there exists...
Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu
a family of strong geometric spanners that admit local
A Characterization of the Degree Sequences of 2-Trees (2006)
Bose, Prosenjit, Dujmović, Vida, Krizanc, Danny, Langerman, Stefan, Morin, Pat, Wood, David R., ...
A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v{i}s a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
Area-Preserving Approximations of Polygonal Paths (2006)
Bose, Prosenjit, Cabello, Sergio, Cheong, Otfried, Gudmundsson, Joachim, Van Kreveld, Marc, Speckmann, Bettina
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Partitions of complete geometric graphs into plane trees (2006)
Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-campo, David R. Wood
Consider the open problem: does every complete geometric graph K 2n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Partitions of complete geometric graphs into plane trees (2006)
Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-campo, Iztapalapa México, David R. Wood
Consider the following question: does every complete geometric graph K2n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2006)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
ABSTRACT. A graph G is a 2-tree if G = K3, or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v is a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine
In the process of developing the second data structure, we develop a new representation of nearest-point and farthest-point Voronoi diagrams of points in convex position. This representation supports...
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, ...
Input: Let P ∈ � d be a set of points lying in convex position. Also given are a point p ∈ P and a halfspace ˆ h ∈ � d. Output: The point q ∈ P which is farthest from p in the halfspace,...
Area-preserving approximations of polygonal paths (2006)
Prosenjit Bose, Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Kreveld, Bettina Speckmann
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Area-preserving approximations of polygonal paths (2006)
Prosenjit Bose, Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Kreveld, Bettina Speckmann
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Rotational clamshell casting in two dimensions (2006)
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed once the liquid has hardened. We consider the case where the object to be...
Incremental Construction of k-Dominating Sets in Wireless Sensor Networks (2006)
Mathieu Couture, Michel Barbeau, Prosenjit Bose, Evangelos Kranakis
Given a graph G, a k-dominating set of G is a subset S of its vertices with the property that every vertex of G is either in S or has at least k neighbors in S. We present a new incremental local...
Rotational clamshell casting in three dimensions (2006)
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed once the liquid has hardened. We consider the case where the object to be...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Partitions of complete geometric graphs into plane trees (2006)
Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-campo, David R. Wood, Politècnica De Catalunya
Consider the open problem: does every complete geometric graph K2n have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line...
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams (2005)
Aronov, Boris, Bose, Prosenjit, Demaine, Erik D., Gudmundsson, Joachim, Iacono, John, Langerman, Stefan, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line l in the...
Simultaneous Diagonal Flips in Plane Triangulations (2005)
Bose, Prosenjit, Czyzowicz, Jurek, Gao, Zhicheng, Morin, Pat, Wood, David R.
Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every $n$-vertex triangulation with at least six vertices has a simultaneous flip into a 4-connected...
Induced Subgraphs of Bounded Degree and Bounded Treewidth (2005)
Bose, Prosenjit, Dujmovic, Vida, Wood, David R.
We prove that for all $0\leq t\leq k$ and $d\geq 2k$, every graph $G$ with treewidth at most $k$ has a `large' induced subgraph $H$, where $H$ has treewidth at most $t$ and every vertex in $H$ has...
Approximate Range Mode and Range Median Queries (2005)
Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang
ABSTRACT. Mode and median are two of the most important statistics we use when we analyze data. In this paper, we consider data structures and algorithms for preprocessing a labelled list of length n...
Abstract A simple polyhedron is weakly-monotonic in direction ~d provided that the intersection of the polyhedron and any plane with normal ~d is simply-connected (i.e. empty, a point, a line-segment...
Approximate Range Mode and Range Median Queries (2005)
Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang
Abstract. We consider data structures and algorithms for preprocessing a labelled list of length n so that, for any given indices i and j we can answer queries of the form: What is the mode or median...
Prosenjit Bose, Marc Van Kreveld, Marc Van Kreveld
A simple polyhedron is weakly-monotonic in direction � d provided that the intersection of the polyhedron and any plane with normal � d is simply-connected (i.e. empty, a point, a line-segment or...
On properties of higherorder Delaunay graphs with applications (2005)
Manuel Abellanas, Prosenjit Bose, Jesús García, Ferran Hurtado, Mariano Nicolás, Pedro A. Ramos
In this work we study the order-k Delaunay graph, which is formed by edges pq having a circle through p and q and containing no more than k sites. We study the combinatorial structure of the set of...
On Simplifying Dot Maps (2004)
De Berg, Mark, Bose, Prosenjit, Cheong, Otfried, Morin, Pat
Dot maps—drawings of point sets—are a well known cartographic method to visualize density functions over an area. We study the problem of simplifying a given dot map: given a set P of points in...
Area-Preserving Approximations of Polygonal Paths (2004)
Bose, Prosenjit, Cabello Justo, S., Cheong, O., Gudmundsson, J., Kreveld, M.J. Van, Speckmann, B.
Reconfiguring Triangulations with Edge Flips and Point Moves (2004)
Aloupis, Greg, Bose, Prosenjit, Morin, Pat
We examine reconfigurations between triangulations and near-triangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration. We show...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
Let denote the average degree, and denote the minimum degree of a graph. An edge is light if both its endpoints have degree bounded by a constant depending only on and. A graph is degree-constrained...
Geodesic ham-sandwich cuts (2004)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
ABSTRACT. Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest...
On local transformations in plane geometric graphs embedded on small grids (2004)
Manuel Abellanas, Prosenjit Bose, Alfredo García, Ferran Hurtado, Pedro Ramos, Eduardo Rivera-campo, ...
Given two n-vertex plane graphs G1 = (V1, E1) and G2 = (V2, E2) with |E1 | = |E2 | embedded in the n × n grid, with straight-line segments as edges, we show that with a sequence of O(n) point moves...
Induced Subgraphs of Bounded Degree and Bounded Treewidth (2004)
Prosenjit Bose, Vida Dujmović, David R. Wood
We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a ‘large ’ induced subgraph H, where H has treewidth at most t and every vertex in H has degree at...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
On simplifying dot maps (2004)
Mark Berg, Prosenjit Bose, Otfried Cheong, Pat Morin
Dot maps—drawings of point sets—are a well known cartographic method to visualize density functions over an area. We study the problem of simplifying a given dot map: given a set P of points in...
Reconfiguring triangulations with edge flips and point moves (2004)
Greg Aloupis, Prosenjit Bose, Pat Morin
Abstract. We examine reconfigurations between triangulations and neartriangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration....
Geodesic ham-sandwich cuts (2004)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
ABSTRACT. Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest...
Geodesic ham-sandwich cuts (2004)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
ABSTRACT. Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest...
Reconfiguring triangulations with edge flips and point moves (2004)
Greg Aloupis, Prosenjit Bose, Pat Morin
Abstract. We examine reconfigurations between triangulations and neartriangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration....
Reconfiguring triangulations with edge flips and point moves (2004)
Greg Aloupis, Prosenjit Bose, Pat Morin
Abstract. We examine reconfigurations between triangulations and neartriangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration....
Approximating Geometric Bottleneck Shortest Paths (2004)
Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
Geodesic ham-sandwich cuts (2004)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
ABSTRACT. Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest...
Feature based cut detection with automatic threshold selection (2004)
Anthony Whitehead, Prosenjit Bose, Robert Laganiere
Abstract. There has been much work concentrated on creating accurate shot boundary detection algorithms in recent years. However a truly accurate method of cut detection still eludes researchers in...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. A three-dimensional (straight-line) grid-drawing...
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
vol., no., pp.-- ()
On Simplifying Dot Maps (2003)
Mark De Berg, Prosenjit Bose, Otfried Cheong, Pat Morin
Dot maps -- drawings of point sets -- are a well known cartographic method to visualize density functions over an area. We study the problem of simplifying a given dot map: given a set P of points in...
The Maximum Number of Edges in a Three-Dimensional Grid-Drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of...
Simultaneous Diagonal Flips in Plane (2003)
Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood
† Research partially completed at Carleton University and McGill University
The maximum number of edges in a three-dimensional grid-drawing (2003)
Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood
An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of...
Prosenjit Bose, Joachim Gudmundsson, Pat Morin
Let V be a set of n points in R . The #-graph of V is a geometric graph with vertex set V that has been studied extensively and which has several nice properties. We introduce a new variant of...
Separating an Object from its Cast (2002)
Ahn, Hee-Kap, De Berg, Mark, Bose, Prosenjit, Cheng, Siu-Wing, Halperin, Dan, Matousek, Jirí, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Computing Signed Permutations of Polygons (2002)
Aloupis, G., Bose, Prosenjit, Demaine, E.D., Langerman, S., Meijer, H., Overmars, M.H., ...
On the spanning ratio of gabriel graphs and β-skeletons (2002)
Prosenjit Bose, Luc Devroye, William Evans, David Kirkpatrick
Abstract. The spanning ratio of a graph defined on n points in the Euclidean plane is the maximum ratio, over all pairs of data points (u, v), of the minimum graph distance between u and v divided by...
Fast approximations for sums of distances, clustering and the Fermat-Weber problem (2002)
Prosenjit Bose, Anil Maheshwari, Pat Morin
We describe two data structures that preprocess a set S of n points in R d (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within...
Fast approximations for sums of distances, clustering and the Fermat-Weber problem (2002)
Prosenjit Bose, Anil Maheshwari, Pat Morin
We describe two data structures that preprocess a set S of n points in R
Asymmetric Communication Protocols Via Hotlink Assignments (2002)
Prosenjit Bose, Danny Krizanc, Stefan Langerman, Pat Morin
We exhibit a relationship between the asymmetric communication problem of Adler and Maggs (1998) and the hotlink assignment problem of Bose et al (2000). By generalizing previous results on the...
Asymmetric communication protocols via hotlink assignments (2002)
Prosenjit Bose, Danny Krizanc, Stefan Langerman, Pat Morin
Abstract. We exhibit a relationship between the asymmetric communication problem of Adler and Maggs (1998) and the hotlink assignment problem of Bose et al (2000). By generalizing previous results on...
Prosenjit Bose, Joachim Gudmundsson, Pat Morin
ABSTRACT. £ Let be a set ¤ of points ¥§ ¦ in. ¨ The-graph £ of is a geometric graph with vertex £ set that has been studied extensively and which has several nice properties. We introduce a...
Translating a Regular Grid over a Point Set (2001)
Bose, Prosenjit, Kreveld, Marc Van, Maheshwari, A. (Anil), Morin, P. (Pat), Morrison, J. (Jason)
We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied...
Bose, Prosenjit, Czyzowicz, J., Hanusse, N., Kranakis, E., Morin, P.
Given a polygon P, a flipturn involves reflecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grünbaum (1995)) showed that any polygon on n vertices...
Competitive online routing in geometric graphs (2001)
We consider online routing algorithms for finding paths between the vertices of plane graphs. Although it has been shown in Bose et al. [3] that there exists no competitive routing scheme that works...
On the Spanning Ratio of Gabriel Graphs and beta-Skeletons (2001)
Prosenjit Bose, Luc Devroye, William Evans, David Kirkpatrick
The spanning ratio of a connected graph defined on n points in the Euclidean plane is the maximal ratio over all pairs of data points (u; v), of the minimum graph distance between u and v, over the...
Competitive online routing in geometric graphs (2001)
We consider online routing algorithms for finding paths between the vertices of plane graphs. Although it has been shown in Bose et al. [4] that there exists no competitive routing scheme that works...
Competitive Online Routing in Geometric Graphs (2001)
We consider online routing algorithms for finding paths between the vertices of plane graphs.
Computing Constrained Minimum-Width Annuli of Point Sets (2000)
Mark De Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami, Gordon Wilfong
We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Online Routing in Convex Subdivisions (2000)
Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, ...
. We consider online routing algorithms for nding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no...
Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. We show that any polygon on n vertices will be convex after any sequence of at most n(n 3)=2...
Hee-Kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Prosenjit Bose, Pat Morin, Antoine Vigneron
Abstract. We consider the following problem. Given a polygon P, possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P,...
Station layouts in the presence of location constraints (1999)
Prosenjit Bose, Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
Prosenjit Bose, Pat Morin, Antoine Vigneron
We consider the following problem. Given a simple polygon P, possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P, and...
Routing with guaranteed delivery in ad hoc wireless networks (1999)
Prosenjit Bose, Pat Morin, Jorge Urrutia
We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some xed...
Routing with guaranteed delivery in ad hoc wireless networks (1999)
Prosenjit Bose, Pat Morin, Jorge Urrutia
We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some xed...
Online routing in triangulations (1999)
Abstract. We consider online routing strategies for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing strategies, one...
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurekk Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
An Improved Algorithm for Subdivision Traversal without Extra Storage (1999)
. We describe an algorithm for enumerating all vertices, edges and faces of a planar subdivision stored in any of the usual pointer-based representations, while using only a constant amount of memory...
Online Routing in Triangulations (1999)
We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing algorithms, one that works...
Routing with Guaranteed Delivery in ad hoc Wireless Networks (1999)
Prosenjit Bose, Pat Morin, Ivan Stojmenovic, Jorge Urrutia
We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some xed...
An Improved Algorithm for Subdivision Traversal without Extra Storage (1999)
We describe an algorithm for enumerating all vertices, edges and faces of a planar subdivision stored in any of the usual pointer-based representations, while using only a constant amount of memory...
Online Routing in Triangulations (1999)
. We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing algorithms, one that...
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
Prosenjit Bose, Pat Morin, Antoine Vigneron
Abstract. We consider the following problem. Given a polygon § , possibly with holes, and having ¨ vertices, compute a pair of equal radius disks that do not intersect each other, are contained in...
Online routing in triangulations (1999)
Abstract. We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing algorithms, one...
Prosenjit Bose, Pat Morin, Antoine Vigneron
ABSTRACT: We consider the following problem. Given a polygon P, possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P,...
Online routing in triangulations (1999)
Abstract. We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing algorithms, one...
Separating an object from its cast (1998)
Ahn, H.K., Berg, M.T. De, Bose, Prosenjit, Halperin, D., Matousek, J., ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
On Embedding an Outer-Planar Graph in a Point Set (1998)
Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(n log³ n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon...
On embedding an outer-planar graph in a point set (1998)
Abstract. Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(n log 3 n) time and O(n) space algorithm to compute a straight-line embedding of G in P,...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Sdndor P. Fckete, Anna Lubiw, Thomas C. Shetruer, Michael E. Houle, Henk Meijer, ...
This paper proposes a 3-dimensional visibility representation of graphs G (V, E) in which vertices are mapped to rectangles floating in [R 3 parallel to the x, y-plane, with edges represented by...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
Testing the quality of manufactured disks and cylinders (1998)
Abstract. We consider the problem of testing the roundness of a manufactured object using the finger probing model of Cole and Yap [2]. When the object being tested is a disk and it's center is...
Testing the quality of manufactured disks and cylinders (1998)
Abstract. We consider the problem of testing the roundness of a manufactured object using the finger probing model of Cole and Yap [1]. When the object being tested is a disk and it's center is...
Testing the Quality of Manufactured Balls (1998)
. We consider the problem of testing the roundness of a manufactured ball, using the nger probing model of Cole and Yap [4]. When the center of the object is known, a procedure requiring O(n 2 )...
Testing the Quality of Manufactured Balls (1998)
We consider the problem of testing the roundness of a manufactured ball, using the finger probing model of Cole and Yap [3]. When the center of the object is known, a procedure requiring O(n 2 )...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...
Prosenjit Bose, Francisco Gómez, Pedro Ramos, Godfried Toussaint
Given a polygonal object (simple polygon, geometric graph, wire-frame, skeleton or more generally a set of line segments) in three-dimensional Euclidean space, we consider the problem of computing a...
Proximity Constraints and Representable Trees, (1997)
Bose, Prosenjit, Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
This paper examines an infinite family of proximity drawings of graphs called open and closed B-drawings, first defined by Kirkpatrick and Radke in the context of computational morphology. Such...
On Rectangle Visibility Graphs (1997)
Bose, Prosenjit, Dean, Alice M., Hutchinson, Joan P., Shermer, Thomas
We study the problem of drawing a graph in the plane so that the vertices of the graph are rectangles that are aligned with the axes, and the edges of the graph are horizontal or vertical...
Optimal Algorithms to Embed Trees in a Point Set (1997)
Prosenjit Bose, Michael Mcallister, Jack Snoeyink
We present optimal ##n log n# time algorithms to solvetwo tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained embeddings. In...
On a Visibility Representation of Graphs in 3D (1997)
Prosenjit Bose, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles floating in R 3 parallel to the x; y-plane, with edges represented by...
Optimal Algorithms to Embed Trees in a Point Set (1997)
Prosenjit Bose, M. McAllister, J. Snoeyink
We present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained...
Separating an Object from its Cast (1997)
Hee-kap Ahn, Mark De Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiri Matousek, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Characterizing and Efficiently Computing Quadrangulations of Planar Point Sets (1997)
Prosenjit Bose, Godfried Toussaint
Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision...
Computing constrained minimum-width annuli of point sets (1996)
Berg, M. De, Bose, Prosenjit, Bremmer, D., Ramaswami, S., Wilfong, G.
Drawing Nice Projections of Objects in Space (1996)
Bose, Prosenjit, Gomez, Francisco, Ramos, Pedro, Toussaint, Godfried
Optimal Algorithms to Embed Trees in a Point Set (1996)
Bose, Prosenjit, McAllister, Michael, Snoeyink, Jack
We present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained...
All Convex Polyhedra can be Clamped with Parallel Jaw Grippers (1996)
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped usingparallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding a suitable location for the pin gate (the pin gate is the point from which liquid is poured or injected into a mold) is a difficult problem when viewed from the...
Proximity Constraints and Representable Trees (1996)
Prosenjit Bose, Giuseppe Di Battista, William Lenhart, Giuseppe Liotta, Roma Italy
This paper examines an infinite family of proximity drawings of graphs called open and closed fi-drawings, first defined by Kirkpatrick and Radke [15, 21] in the context of computational morphology....
Approximating Shortest Paths in Arrangements of Lines (1996)
Prosenjit Bose, William Evans, David Kirkpatrick, Michael McAllister, Jack Snoeyink
this paper, we study the problem of computing the shortest path between a pair of points on an arrangement of lines with respect to the Euclidean distance metric. Let L = f` 1 ; ` 2 ; : : : ; ` n g...
Prosenjit Bose, Godfried Toussaint
Given an n vertex simple polygon M , we show how to compute the Euclidean center of M constrained to lie in the interior of M , in a polygonal region inside M or on the boundary of M in O(n log n +...
Computing Constrained Minimum-Width Annuli of Point Sets (1996)
Mark De Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami, Gordon Wilfong
. We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
Geometric and computational aspects of manufacturing processes /--by Prosenjit K. Bose. (1995)
Abstracts in English and French.
Proximity Constraints and Representable Trees (extended abstract) (1995)
Bose, Prosenjit, Di Battista, Giuseppe, Lenhart, William, Liotta, Giuseppe
A family of proximity drawings of graphs called open and closed \beta-drawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete...
Growing a tree from its branches (1995)
Prosenjit Bose, Godfried Toussaint, Ha A
Given a set of n disjoint line segments in the plane, we show that it is always possible to form a spanning tree of the endpoints of the segments, such that each line segment is an edge of the tree...
Growing a tree from its branches (1995)
Prosenjit Bose, Godfried Toussaint, Ha A
Given a set L of n disjoint line segments in the plane, we show that it is always possible to form a spanning tree of the endpoints of the segments, such that each line segment is an edge of the tree...
Geometric and computational aspects of gravity casting (1995)
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after the termination of the gravity casting process is an important and...
No Quadrangulation is Extremely Odd (1995)
Prosenjit Bose, Godfried Toussaint
Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision...
Growing a Tree from its Branches (1995)
Prosenjit Bose, Godfried T. Toussaint, Ha A
Given a set L of n disjoint line segments in the plane, we show that it is always possible to form a spanning tree of the endpoints of the segments, such that each line segment is an edge of the tree...
On a Visibility Representation for Graphs in Three Dimensions (1995)
Prosenjit Bose, Qu'ebec Ga H, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, ...
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
Optimal algorithms to embed trees in a point set (1995)
Prosenjit Bose, Michael Mcallister, Jack Snoeyink
We present optimal Θ(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained embeddings. In...
Determining the castability of simple polyhedra (1994)
Bose, Prosenjit, Kreveld, M.J. Van
A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured easily using two cast parts, where each cast part can be...
Geometric and computational aspects of manufacturing processes (1994)
Two of the fundamental questions that arise in the manufacturing industry concerning every type of manufacturing process are: (1) Given an object, can it be built using a particular process? (2)...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
Prosenjit Bose, David Bremner, Godfried Toussaint
Abstract We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
Determining the Castability of Simple Polyhedra (1994)
Prosenjit Bose, David Bremner, Marc Van Kreveld
A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured easily using two cast parts, where each cast part can be...
Geometric and computational aspects of manufacturing processes (1994)
Two of the fundamental questions that arise in the manufacturing industry concerning every type of manufacturing process are: (1) Given an object, can it be built using a particular process? (2)...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2, given n points in the plane and a tripartition k1 + k2 + k3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge contains...
Pattern Matching For Permutations (1993)
Prosenjit Bose, Jonathan F. Buss, Anna Lubiw
Given a permutation T of 1 to n, and a permutation P of 1 to k, for k n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P . For example, if P is...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2pi, given n points in the plane and a tripartition k 1 + k 2 + k 3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge...
Feasibility of Design in Stereolithography (1993)
Boudewijn Asberg, Gregoria Blanco, Prosenjit Bose, Jesus Garcia-lopez, Mark Overmars, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2ß, given n points in the plane and a tripartition k 1 + k 2 + k 3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge...
Filling Polyhedral Molds (1993)
Prosenjit Bose, Marc Van Kreveld, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after termination of the gravity casting process, is an important and...
On a Visibility Representation for Graphs in Three Dimensions (1993)
Prosenjit Bose, Hazel Everett, Sandor P. Fekete, Anna Lubiw, Henk Meijer, Kathleen Romanik, ...
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
Guarding Polyhedral Terrains (1992)
Prosenjit Bose, Thomas Shermer, Godfried Toussaint, Binhai Zhu
We prove that b n 2 c vertex guards are always sufficient and sometimes necessary to guard the surface of an n-vertex polyhedral terrain. We also show that b (4n\Gamma4) 13 c edge guards are...
All Convex Polyhedra can be Clamped with Parallel Jaw Grippers
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
On Rectangle Visibility Graphs
Prosenjit Bose, Alice Dean, Joan Hutchinson, Thomas Shermer
this paper we consider the problem of drawing a graph in the plane so that the vertices of the graph are drawn as rectangles and the edges are horizontal or vertical line segments. We are in...
Geometric and Computational Aspects of Gravity Casting
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after the termination of the gravity casting process is an important and...