Dujmovic, Vida, Howat, John, Morin, Pat
A data structure, called a biased range tree, is presented that preprocesses a set S of n points in R^2 and a query distribution D for 2-sided orthogonal range counting queries. The expected query...
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...
Distinct Distances in Graph Drawings (2008)
Carmi, Paz, Dujmović, Vida, Morin, Pat, Wood, David R.
The \emph{distance-number} of a graph $G$ is the minimum number of distinct edge-lengths over all straight-line drawings of $G$ in the plane. This definition generalises many well-known concepts in...
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...
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...
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...
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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2004)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
Unfolding Polyhedral Bands (2004)
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Ileana Streinu, Godfried Toussaint
A band is de ned as the intersection of the surface of a convex polyhedron with the space between two parallel planes, as long as this space does not contain any vertices of the polyhedron. An...
Layout of Graphs with Bounded Tree-Width (2004)
A queue layout of a graph consists of a total order of the vertices, and a partition of the edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a...
Layout of Graphs with Bounded Tree-Width (2004)
Dujmovic, Vida, Morin, Pat, Wood, David R.
A \emph{queue layout} of a graph consists of a total order of the vertices, and a partition of the edges into \emph{queues}, such that no two edges in the same queue are nested. The minimum number of...
Improving Distance Based Geographic Location (2004)
Michel Barbeau, Evangelos Kranakis, Danny Krizanc, Pat Morin
Supporting nodes without Global Positioning System (GPS) capability, in wireless ad hoc and sensor networks, has numerous applications in guidance and surveying systems in use today. At issue is that...
Three-Dimensional 1-Bend Graph Drawings (2004)
We consider three-dimensional grid-drawings of graphs with at most one bend per edge. Under the additional requirement that the vertices be collinear, we prove that the minimum volume of such a...
Competitive Online Routing in Geometric Graphs (2004)
We consider online routing algorithms for finding paths between the vertices of plane graphs.
On the False-Positive Rate of Bloom Filters (2004)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
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 the...
Approximate Range Mode And Range Median Queries (2004)
Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang
We consider data structures and algorithms for preprocessing a labelled list of length n so that, for any given i and j we can answer queries of the form: What is the mode or median label in the...
Geodesic Ham-Sandwich Cuts (2004)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
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...
The Maximum Number of Edges in a Three-Dimensional Grid-Drawing (2004)
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...
Journal of Graph Algorithms and Applications (2004)
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...
Wireless Networks 0 (2001) ?--? 1 Routing with Guaranteed Delivery (2004)
Prosenjit Bose, Pat Morin, Ivan Stojmenovic, Jorge Urrutia
this paper, we consider routing in manets for which hosts know nothing about the network except their location and the locations of the hosts to which they can communicate directly. In particular, we...
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...
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...
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...
Geodesic Ham-Sandwich Cuts (2003)
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Pat Morin
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...
On Worst Case Robin-Hood Hashing (2003)
Luc Devroye, Pat Morin, Alfredo Viola
We consider open addressing hashing, and implement it by using the Robin Hood strategy, that is, in case of collision, the element that has traveled the furthest can stay in the slot. We hash #n...
Packing Two Disks into a Polygonal Environment (2003)
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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2003)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
The Geometry of Carpentry and Joinery (2003)
In this paper we propose to model a simplified wood shop. Following the work of Demaine, Demaine and Kaplan in [1] we limit the cutting tools of our carpenter to a circular saw. We extend that...
Computing The Center Of Area Of A Convex Polygon (2003)
Peter Bra, Laura Heinrich-litan, Pat Morin
this paper we give a simple randomized linear-time algorithm for finding the center of area of a convex n-gon P , which also computes Winternitz's measure of symmetry for P . We proceed by first...
Range Mode And Range Median Queries On Lists And Trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range Mode And Range Median Queries On Lists And Trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range Mode and Range Median Queries on Lists and Trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range Mode and Range Median Queries on Lists and Trees (2003)
Krizanc, Danny, Morin, Pat, Smid, Michiel
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
On Simplifying Dot Maps (2003)
Mark De Berg, 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...
Space-Efficient Planar Convex Hull Algorithms (2003)
Herve Bronnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-e#cient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-e#cient...
Testing the Quality of Manufactured Disks and Balls (2003)
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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2003)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2003)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R [ B comes from R...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2003)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
Asymmetric Communication Protocols Via Hotlink Assignments (2003)
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...
The Maximum Number of Edges in a Three-Dimensional Grid-Drawing (2003)
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.
Space-Efficient Planar Convex Hull Algorithms (2003)
John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-ecient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-ecient...
Putting Your Dictionary On A Diet (2002)
We show that any comparison-based dictionary data structure that requires cn memory in addition to the storage required for the data elements can be transformed into a dictionary that requires only n...
On Worst Case Robin-Hood Hashing (2002)
Luc Devroye, Pat Morin, Alfredo Viola
We consider open addressing hashing, and implement it by using the Robin Hood strategy, that is, in case of collision, the element that has traveled the furthest can stay in the slot. We hash #n...
The Maximum Number of Edges in a Three-Dimensional Grid-Drawing (2002)
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.
Cuckoo Hashing: Further Analysis (2002)
We consider cuckoo hashing as proposed by Pagh and Rodler in 2001. We show that the expected construction time of the hash table is O(n) as long as the two open addressing tables are each of size at...
A Framework for Multiresolution Modelling (2002)
Anil Maheshwari, Pat Morin, Jorg-rudiger Sack
Introduction The subject of multiresolution surface modelling has received considerable attention from a number of fields, including computational geometry, geographic information systems, and...
Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees and Cycles (2002)
Stefan Langerman, Pat Morin, Michael Soss
The maximum detour and spanning ratio of an embedded graph G are values that measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...
Pathwidth and Three-Dimensional (2002)
Vida Dujmovic, Pat Morin, David R. Wood
We prove that every n-vertex graph G with pathwidth pw(G) has a three-dimensional straight-line grid drawing with O(pw(G) n) volume.
Covering Points with Lines (2002)
Given a set of n points in the plane, is it possible to nd k lines that cover all the points in the set? We show that although this problem is NPhard, it can be solved eciently for small values of k....
On Worst Case Robin-Hood Hashing (2002)
Luc Devroye, Pat Morin, Alfredo Viola
We consider open addressing hashing, and implement it by using the Robin Hood strategy, that is, in case of collision, the element that has traveled the furthest can stay in the slot. We hash #n...
Translating a Regular Grid over a Point Set (2002)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or in nite) 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 if...
Fast Approximations for Sums of Distances, (2002)
Prosenjit Bose, Anil Maheshwari, Pat Morin
We describe two data structures that preprocess a set S of n points in R (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a...
Progressive TINs: Algorithms and Applications (2002)
Anil Maheshwari, Pat Morin, Jorg-rudiger Sack
Transmission of geographic data over the Internet, rendering at different resolutions /levels of detail, or processing at unnecessarily fine detail pose interesting challenges and opportunities. In...
Wireless Networks 0 (2001) ?{? 1 Routing with Guaranteed Delivery (2002)
Prosenjit Bose, Pat Morin, Jorge Urrutia
this paper, we consider routing in manets for which hosts know nothing about the network except their location and the locations of the hosts to which they can communicate directly. In particular, we...
Progressive TINs: Algorithms and Applications (2002)
Anil Maheshwari, Pat Morin, Jorg-rudiger Sack
Transmission of geographic data over the Internet, rendering at different resolutions/levels of detail, or processing at unnecessarily fine detail pose interesting challenges and opportunities. In...
Provably Secure and Efficient Block Ciphers (2002)
The security and efficiency of two recently proposed block ciphers, bear and lion, both based on a hash function and a stream cipher, is discussed. Meet-inthe -middle attacks are presented which can...
Coarse Grained Parallel Computing on Heterogeneous Systems (2002)
Coarse grained parallel (CGP) computing models such as the coarse grained multicomputer (CGM), bulk synchronous parallel (BSP), and LogP models have received considerable attention recently from the...
Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
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...
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Vida Dujmovic, Pat Morin, David R. Wood
We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)^2 n) volume.
On Simplifying Dot Maps (2002)
Mark Berg, Proscnjit Bose, Otfried Chcong, Pat Morin
Dot maps drawings of point setsre a well known carlographic method to visualize density fimclions over an area. We study the problem of simplifying a given dot map: given a set P of points ill tile...
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...
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...
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...
Competitive Online Routing in Geometric Graphs (2002)
We consider online routing algorithms for finding paths between the vertices of plane graphs.
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 constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a...
Fast Approximations for Sums of Distances, Clustering and the Fermat-Weber Problem (2002)
We describe two data structures that preprocess a set S of n points in R (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a...
Translating a Regular Grid over a Point Set (2002)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or in nite) 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 if...
Packing Two Disks into a Polygonal Environment (2002)
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...
Online Routing in Convex Subdivisions (2002)
Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, J. Ian Munro
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...
Routing with Guaranteed Delivery in (2002)
this paper, we consider routing in manets for which hosts know nothing about the network except their location and the locations of the hosts to which they can communicate directly. In particular, we...
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Vida Dujmovic, Pat Morin, David R. Wood
We prove that every n-vertex graph G with pathwidth pw(G) has a three-dimensional straight line grid drawing with O(pw(G) n) volume. Thus for graphs with bounded pathwidth the volume is O(n), and it...
In-Place Planar Convex Hull Algorithms (2002)
John Iacono, Jyrki Katajainen, Pat Morin
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
Packing Two Disks into a Polygonal Environment (2002)
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...
Translating a Regular Grid over a Point Set (2002)
Bose, Prosenjit, Kreveld, Marc Van, Maheshwari, Anil, Morin, Pat, Morrison, Jason
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Dujmovic, Vida, Morin, Pat, Wood, David R.
We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)² *n) volume. Thus for graphs with bounded path-width the volume is O(n),...