Pat Morin

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...

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)

Pat Morin

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)

Pat Morin

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)

Luc Devroye, Pat Morin

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)

Pat Morin

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...

Biased Range Trees (2008)

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...

Abstract (2008)

Pat Morin

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...

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...

Abstract (2008)

Pat Morin

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)

Stefan Langerman, Pat Morin

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)

Pat Morin, Jason Morrison

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...

Clamshell Casting ∗ (2008)

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)

Pat Morin

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...

Flipping your lid (2008)

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...

PROSENJIT BOSE (2008)

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)

Prosenjit Bose, Pat Morin

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...

Algorithms for Optimal Outlier Removal 1 Abstract Rossen Atanassov, Prosenjit Bose, Mathieu Couture, (2008)

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)

Pat Morin

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...

Ordered Theta Graphs (2008)

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)

Pat Morin, Pat Morin

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)

Pat Morin

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...

z (2007)

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...

y (2007)

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)

Pat Morin April, Pat Morin

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)

Pat Morin

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)

Pat Morin

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)

Pat Morin

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)

Pat Morin

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...

2 1 (2007)

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)

Stefan Langerman, Pat Morin

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....

Pedeciba Informatica (2007)

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...

4 (2007)

David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...

Computer Science Department, University of Illinois,

2 (2007)

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...

x (2007)

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)

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,...

z (2007)

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...

Wesleyan University (2007)

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)

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,...

z (2007)

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...

a (2007)

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...

Wireless Networks (2007)

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...

On Cutting and Gluing (2007)

Pat Morin, Jason Morrison

We study the problem of building a polygon P by gluing together strips of wood and cutting them with a circular saw. 1

z (2007)

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...

Prosenjit Bose y (2007)

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...

Ordered Theta Graphs (2007)

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)

Prosenjit Bose, Pat Morin

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...

2 (2007)

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)...

4 (2007)

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)

Pat Morin

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)

Prosenjit Bose, Pat Morin

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,...

ARTICLE IN PRESS COMGEO:889 JID:COMGEO AID:889 /FLA [m3SC+; v 1.70; Prn:5/04/2007; 14:09] P.1 (1-16) Computational Geometry •• • (••••) •••–••• (2007)

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...

Contributors (2006)

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

An optimal randomized algorithm for d-variate zonoid depth. Submitted to Computational Geometry: Theory and Applications (2006)

Pat Morin

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 � � � �...

An optimal randomized algorithm for d-variate zonoid depth. Submitted to Computational Geometry: Theory and Applications (2006)

Pat Morin

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)

Pat Morin, David R. Wood

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)

Pat Morin, David R. Wood

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)

Pat Morin, David R. Wood

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)

Luc Devroye, Pat Morin

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...

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...

Pedeciba Informatica (2003)

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...

Ordered Theta Graphs (2003)

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...

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),...

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...

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...

Ordered theta graphs (2002)

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)

Prosenjit Bose, Pat Morin

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)

Pat Morin, Jason Morrison

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)

Prosenjit Bose, Pat Morin

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)

Luc Devroye, Pat Morin

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)

Luc Devroye, Pat Morin

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)

Prosenjit Bose, Pat Morin

We consider online routing algorithms for finding paths between the vertices of plane graphs.

Flipping your Lid (2000)

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...

Flipping Your Lid (2000)

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...

Flipping your Lid (2000)

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...

Flipping your Lid (2000)

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...

Flipping Your Lid (2000)

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...

6 On difference in being see PN 449a14-9, DA iii.7 431a13-4, Met. xiii.2 1077b1-4, etc. In contexts where this locution is employed Aristotle generally draws attention to the fact that coextensive things may nevertheless have different accounts of their b (1999)

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,...

6 On difference in being see PN 449a14-9, DA iii.7 431a13-4, Met. xiii.2 1077b1-4, etc. In contexts where this locution is employed Aristotle generally draws attention to the fact that coextensive things may nevertheless have different accounts of their b (1999)

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)

Prosenjit Bose, Pat Morin

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)

Prosenjit Bose, Pat Morin

. 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)

Prosenjit Bose, Pat Morin

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)

Prosenjit Bose, Pat Morin

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)

Prosenjit Bose, Pat Morin

. 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...

6 On difference in being see PN 449a14-9, DA iii.7 431a13-4, Met. xiii.2 1077b1-4, etc. In contexts where this locution is employed Aristotle generally draws attention to the fact that coextensive things may nevertheless have different accounts of their b (1999)

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)

Prosenjit Bose, Pat Morin

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...

6 On difference in being see PN 449a14-9, DA iii.7 431a13-4, Met. xiii.2 1077b1-4, etc. In contexts where this locution is employed Aristotle generally draws attention to the fact that coextensive things may nevertheless have different accounts of their b (1999)

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)

Prosenjit Bose, Pat Morin

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)

Prosenjit Bose, Pat Morin

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)

Prosenjit Bose, Pat Morin

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)

Prosenjit Bose, Pat Morin

. 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)

Prosenjit Bose, Pat Morin

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)

Pat Morin

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)

Pat Morin School, Pat Morin

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...

A Critique of BEAR and LION

Pat Morin

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)...