Memoryless Routing in Convex Subdivisions: Random Walks are Optimal (2009)
Chen, Dan, Devroye, Luc, Dujmovic, Vida, Morin, Pat
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coordinates of v, t,...
Notes on large angle crossing graphs (2009)
Dujmovic, Vida, Gudmundsson, Joachim, Morin, Pat, Wolle, Thomas
A graph G is an a-angle crossing (aAC) graph if every pair of crossing edges in G intersect at an angle of at least a. The concept of right angle crossing (RAC) graphs (a=Pi/2) was recently...
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,...
On the Expected Maximum Degree of Gabriel and Yao Graphs (2009)
Devroye, Luc, Gudmundsson, Joachim, Morin, Pat
Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximal degree of a random Gabriel graph or Yao graph defined on $n$ points drawn uniformly at...
Algorithms for Marketing-Mix Optimization (2009)
Gudmundsson, Joachim, Morin, Pat, Smid, Michiel
Algorithms for determining quality/cost/price tradeoffs in saturated markets are considered. A product is modeled by $d$ real-valued qualities whose sum determines the unit cost of producing the...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2009)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
2 Basic Blocks as DAGs 3 Basic Blocks as DAGs (2009)
Pat Morin, Like Expressions, As Dags
• Register allocation by graph coloring
Entropy, Triangulation, and Point Location in Planar Subdivisions (2009)
Collette, Sebastien, Dujmovic, Vida, Iacono, John, Langerman, Stefan, Morin, Pat
A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a...
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...
REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
Abstract. For n ∈ , we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple...
Point Location in an Arrangement (2008)
Consider the following special case of planar point location: preprocess k sets of lines, where each set consists of parallel lines, to support queries of the form “given a point p, what is the...
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...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of...
Realizing Partitions Respecting Full and Partial Order Information (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of...
Origins of the Internet (Cont'd) • Leonard Kleinrock at MIT published the first paper (2008)
and book in packet switching theory in 1961 and 1964, respectively. • Kleinrock convinced Laurence G. Roberts of the theoretical feasibility of the project. 4 Origins of the Internet (Cont'd)...
MINIMALIST APPROXIMATIONS FOR CONVEX FUNCTIONS Prosenjit Bose (2008)
ABSTRACT. We study data structures for approximating convex functions whose slopes are bounded as well as applications of such data structures to problems in clustering and facility location. 1
Point Location in an Arrangement (2008)
Consider the following special case of planar point location: preprocess k sets of lines, where each set consists of parallel lines, to support queries of the form “given a point p, what is the...
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...
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...
We consider online routing algorithms for finding paths between the vertices of plane graphs. We show there exists a simple online O(1)-memory c-competitive routing strategy that approximates the...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2008)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
DISTRIBUTION-SENSITIVE POINT LOCATION IN CONVEX SUBDIVISIONS ∗ (2008)
Sébastien Collette, John Iacono, Pat Morin, Stefan Langerman
ABSTRACT. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is...
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...
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...
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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. 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...
DISTRIBUTION-SENSITIVE POINT LOCATION IN CONVEX SUBDIVISIONS ∗ (2008)
Sébastien Collette, Stefan Langerman, Vida Dujmović, John Iacono, ...
ABSTRACT. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that...
Distribution-Sensitive Point Location in Convex Subdivisions 1 (2008)
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin
Abstract. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. If the optimal data structure in the linear decision...
Abstract Space-Efficient Planar Convex Hull Algorithms 1 (2008)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient 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...
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...
Covering Points with Lines (2008)
Given a set of n points in the plane, is it possible to find k lines that cover all the points in the set? We show that although this problem is NPhard, it can be solved efficiently for small values...
The Geometry of Carpentry and Joinery ⋆ (2008)
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...
REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
Abstract. For n ∈ �, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple...
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...
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...
Heterogeneous Coarse-Grained Parallel Computing (2008)
Abstract We consider the problem of finding efficient parallel algorithms for heterogeneous parallel computers, i.e., parallel computers in which different processors have different computational...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0,n) into k subintervals of positive integer lengths ℓ1,...,ℓk such that the lengths satisfy a set of simple constraints of the...
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...
Hotlink Assignments, 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...
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...
Computing the detour and spanning ratio of paths, trees and cycles in 2D and 3D (2008)
Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, ...
The detour and spanning ratio of a graph � embedded in �� � measure how well � approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. 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...
Anil Maheshwari, Pat Morin, Michel Paquette, Michiel Smid, Stefanie Wuhrer
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 diameter,...
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...
DISTRIBUTION-SENSITIVE POINT LOCATION IN CONVEX SUBDIVISIONS ∗ (2008)
Sébastien Collette, John Iacono, Pat Morin, Stefan Langerman
ABSTRACT. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is...
Nordic Journal of Computing RANGE MODE AND RANGE MEDIAN QUERIES ON LISTS AND TREES ∗ (2008)
Danny Krizanc, Pat Morin, Michiel Smid
Abstract. 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...
OUTPUT-SENSITIVE ALGORITHMS FOR COMPUTING NEAREST-NEIGHBOUR DECISION BOUNDARIES ∗ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
ABSTRACT. 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...
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...
PUTTING YOUR DICTIONARY ON A DIET (2008)
ABSTRACT. 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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
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 (2008)
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...
Prosenjit Bose Joachim, 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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
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...
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...
1 Heterogeneous Coarse-Grained Parallel Computing (2007)
We consider the problem of finding efficient parallel algorithms for heterogeneous parallel computers, i.e., parallel computers in which different processors have different computational potential....
ONLINE ROUTING IN TRIANGULATIONS PROSENJIT BOSE (2007)
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...
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...
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
An Extensible Implementation of a Balanced Binary Tree (2007)
this paper, we study a very concrete example of this problem. Namely, we consider the problem of designing an extensible implementation of a balanced binary search tree. We consider several different...
Deflating Quadrilaterals (2007)
We study the process of deating quadrilaterals using the deation operator (Wegner 1993), which is the inverse of the pocket ip, or simply, ip operator (Grunbaum 1995). In particular, we characterize...
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...
Online Algorithms and Game Theory (2007)
The relationships between online algorithms and classical game theory are discussed. This discussion includes modeling online problems as two player zero-sum games, the use of Yao's principle in...
The Role of Reductions in Cryptography (2007)
Reductions have long been used in studying the security of cryptographic systems and protocols. The role of reductions in cryptography is examined and a number of examples of the use of reductions in...
Optimal Randomized Parallel Algorithms for Computational Geometry (2007)
A summary of the results achieved in the paper "Optimal Randomized Parallel Algorithms for Computational Geometry," by Reif and Sen is given. These results include optimal randomized PRAM...
Vida Dujmovic, Pat Morin, David R. Wood
Abstract. We prove that every n-vertex graph G with pathwidth pw(G) has a three-dimensional straight-line grid drawing with O(pw(G) 2 n) volume. Thus for graphs with bounded pathwidth the volume is...
Covering Points with Lines (2007)
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....
Luc Devroye, Pat Morin, Alfredo Viola
Abstract. 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...
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
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...
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...
Packing Two Disks into a Polygonal Environment Prosenjit Bose 1 (2007)
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,...
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...
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...
Packing Two Disks into a Polygonal Environment Prosenjit Bose 1 (2007)
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,...
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
z Universite du Quebec a Hull.
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...
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...
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...
Ordered Theta Graphs y Prosenjit Bose z (2007)
Joachim Gudmundsson, Pat Morin
Let V be a set of n points in R 2. 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...
n). No better bound than O(n (2007)
Vida Dujmovic, Pat Morin, David R. Wood
We prove that every n-vertex graph G with pathwidth pw(G) has a threedimensional straight line grid drawing with O(pw(G) 2 n) volume. Thus for graphs with bounded pathwidth the volume is O(n), and it...
Translating a Regular Grid over a Point Set* (2007)
Marc Van Kret, Anil Maheshwari, Pat Morin, Pat Morin, Jason Morrison, Jason Morrison
We consider the problem of translating a (finite or infinite) squoxe 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...
We study the problem of building a polygon P by gluing together strips of wood and cutting them with a circular saw. 1
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Figure 1: An example of a ipturn. Given a polygon P, a ipturn involves re ecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed...
Unfolding Polyhedral Bands (2007)
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, ...
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...
On Worst Case Robin-Hood Hashing (2007)
Luc Devroye Pat, 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...
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...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2007)
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...
In-Place Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
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...
Space-Efficient Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient 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...
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...
A Framework for Multiresolution Modelling (2007)
Anil Maheshwari, Pat Morin, Jörg-Rüdiger Sack
Introduction The subject of multiresolution surface modelling has received considerable attention from a number of fields, including computational geometry, geographic information systems, and...
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)...
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
Putting Your Dictionary on a Diet (2007)
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...
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...
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 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...
RANDOMIZED RENDEZ-VOUS WITH LIMITED MEMORY (2007)
Evangelos Kranakis, Danny Krizanc, Pat Morin
Abstract. We present a tradeoff between the expected time for two identical agents to rendez-vous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular,...
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...
Putting your data structure on a diet (2007)
Hervé Brönnimann, Jyrki Katajainen, Pat Morin
Abstract. Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several...
Putting your data structure on a diet (2007)
Hervé Brönnimann, Jyrki Katajainen, Pat Morin
Abstract. Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several...
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...
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...
Outputsensitive algorithms for Tukey depth and related problems, Submitted (2006)
David Bremner, Stefan Langerman, Dan Chen, Pat Morin, John Iacono
ABSTRACT. The Tukey depth (Tukey 1975) of a point p with respect to a finite set S of points is the minimum number of elements of S contained in any closed halfspace that contains p. Algorithms for...
Jyrki Katajainen, Gerth Stølting Brodal, Hervé Brönnimann, Manuel Macías Córdoba, Miguel Fiandor Gutiérrez, Kasper Egdø, ...
This volume contains the papers presented at the 6th STL Workshop which was
Abstract. A randomized linear expected-time algorithm for computing the zonoid depth (Dyckerhoff et al 1996, Mosler 2002) of a point with respect to a fixed dimensional point set is presented. 1
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...
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...
Removing outliers to minimize area and perimeter (2006)
Rossen Atanassov, Pat Morin, Stefanie Wuhrer
We consider the problem of removing c points from a set S of n points so that the resulting point set has the smallest possible convex hull. Our main result is an O � n � � � � � 4c c 2c...
Removing outliers to minimize area and perimeter (2006)
Rossen Atanassov, Pat Morin, Stefanie Wuhrer
We consider the problem of removing c points from a set S of n points so that the resulting point set has the smallest possible convex hull. Our main result is an O � n � � � � � 4c c 2c...
Outputsensitive algorithms for Tukey depth and related problems, Submitted (2006)
David Bremner, Dan Chen, John Iacono, Stefan Langerman, Pat Morin
ABSTRACT. The Tukey depth (Tukey 1975) of a point p with respect to a finite set S of points is the minimum number of elements of S contained in any closed halfspace that contains p. Algorithms for...
Removing outliers to minimize area and perimeter (2006)
Rossen Atanassov, Pat Morin, Stefanie Wuhrer
Abstract. We consider the problem of removing c points from a set S of n points so that the resulting point set has the smallest possible convex hull. Our main result is an O � n � � � �...
Abstract. A randomized linear expected-time algorithm for computing the zonoid depth (Dyckerhoff et al 1996, Mosler 2002) of a point with respect to a fixed dimensional point set is presented. 1
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...
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...
Approximate Range Mode And Range Median Queries (2005)
Prosenjit Bose Evangelos, 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...
3D£Ý Computing the Detour and Spanning Ratio of Paths, Trees and Cycles in 2D and (2005)
Pankaj K. Agarwalþ, Rolf Kleinü, Christian Knauerß, Stefan Langerman, Pat Morin, Micha Sharirýý, ...
The detour and spanning ratio of a graph�embedded in��measure how well�approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describeÇÒÐÓ�Òtime...
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...
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...
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...
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...
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...
Improving Distance Based Geographic Location Techniques (2004)
Michel Barbeau, Evangelos Kranakis, Danny Krizanc, Pat Morin
Abstract. 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...
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...
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...
On Worst Case Robin-Hood Hashing (2004)
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 farthest can stay in the slot. We hash ∼ αn...
Layout of Graphs with Bounded Tree-Width (2004)
Vida Dujmovic, Pat Morin, David R. Wood
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...
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....
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...
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....
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...
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...
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...
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...
Cuckoo Hashing: Further Analysis (2003)
Abstract. 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...
Range mode and range median queries on lists and trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
ABSTRACT. 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...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) 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...
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. A three-dimensional (straight-line) grid-drawing...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) 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...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) 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...
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...
Computing the Center of Area of a Convex Polygon (2003)
Peter Braß, Laura Heinrich-litan, Pat Morin
The center of area of a convex planar set X is the point...
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...
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...
Translating a regular grid over a point set (2003)
Anil Maheshwari, Pat Morin, Jason Morrison
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...
Luc Devroye, Pat Morin, Alfredo Viola
Abstract. 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...
Range Mode And Range Median Queries On Lists And Trees (2003)
Danny Krizanc Wesleyan, 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...
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
Cuckoo hashing: Further analysis (2003)
Luc Devroye, Pat Morin, Communicated F. Dehne
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...
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...
Range mode and range median queries on lists and trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
Abstract. 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...
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...
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),...
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),...
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),...
Fast approximations for sums of distances, clustering and the Fermat-Weber problem (2002)
Carleton University
Computing the maximum detour and spanning ratio of planar chains, trees and cycles (2002)
Stefan Langerman, Pat Morin, Michael Soss
Let G = (V, E) be an embedded connected graph with n vertices and m edges. Specifically, the vertex set V consists of points in R 2, and E consists
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...
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...
Space-efficient planar convex hull algorithms (2002)
Herve Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient 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...
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...
Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs (2002)
Vida Dujmovic, Pat Morin, David Wood
We prove that every n-vertex graph with path-width pw(G) a three-dimensional straight-line drawing with O(pw(G) u-g Thu graphs with bou58j path-width volu7 is O(n), follows that graphs with bou602...
Computing the maximum detour and spanning ratio of planar chains, trees and cycles (2002)
Stefan Langerman, Pat Morin, Michael Soss
Abstract. 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...
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...
Optimal in-place planar convex hull algorithms (2002)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Godfried Toussaint
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...
Layout of graphs with bounded tree-width (2002)
Vida Dujmović, Pat Morin, R. Wood
Abstract. 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...
Path-width and three-dimensional straight-line grid drawings of graphs (2002)
Vida Dujmović, Pat Morin, David R. Wood
Abstract. We prove that every-vertex graph with pathwidth has a three-dimensional straight-line grid drawing with volume. Thus for graphs with bounded pathwidth the volume is, and it follows that for...
c ○ World Scientific Publishing Company COMPUTING THE CENTER OF AREA OF A CONVEX POLYGON ∗ (2002)
Peter Braß, Laura Heinrich-litan, Pat Morin
Communicated by Pankaj K. Agarwal The center of area of a convex planar set X is the point p for which the minimum area of X intersected by any halfplane containing p is maximized. We describe a...
Computing the center of area of a convex polygon (2002)
Peter Braß, Laura Heinrich-litan, Pat Morin
ABSTRACT. The center of area of a convex planar set ¤ is the point ¥ for which the minimum area of ¤ intersected by any halfplane containing ¥ is maximized. We describe a simple randomized...
Layout of graphs with bounded tree-width (2002)
Vida Dujmovi Ć, Pat Morin, R. Wood
Abstract. 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...
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...
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...
Packing two disks into a polygonal environment (2001)
Bose, Prosenjit, Morin, Pat, Vigneron, Antoine
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...
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...
The Geometry of Carpentry and Joinery (2001)
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...
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...
Cuckoo Hashing: Further Analysis (2001)
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...
Cuckoo Hashing: Further Analysis (2001)
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...
Competitive Online Routing in Geometric Graphs (2001)
We consider online routing algorithms for finding paths between the vertices of plane graphs.
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...
Convexifying Polygons with Simple Projections (2000)
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
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...
Online Routing in Convex Subdivisions (2000)
Prosenjit Bose Andrej, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Pat Morin, ...
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, 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,...
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...
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...
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...
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 )...
Coarse Grained Parallel Computing on Heterogeneous Systems (1998)
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...
Progressive TINs: Algorithms and applications (1997)
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...
Progressive TINs: Algorithms and Applications (1997)
Anil Maheshwari, Pat Morin, Jörg-Rüdiger 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 (1996)
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...
The paper "Two Practical and Provably Secure Block Ciphers: BEAR and LION" [AnBi96] by Ross Anderson and Eli Biham is summarized. The paper presents two new block ciphers (BEAR and LION)...