Publications (48)
On the Expected Maximum Degree of Gabriel and Yao Graphs
Luc Devroye, Joachim Gudmundsson, Pat Morin
Notes on Growing a Tree in a Graph
Luc Devroye, Vida DujmoviÄ, Alan Frieze +3
Biased Predecessor Search
Prosenjit Bose, Rolf Fagerberg, John Howat +1
A Note on Interference in Random Point Sets
Luc Devroye, Pat Morin
Entropy, Triangulation, and Point Location in Planar Subdivisions
Sebastien Collette, Vida Dujmovic, John Iacono +2
Succinct Geometric Indexes Supporting Point Location Queries
Prosenjit Bose, Eric Y. Chen, Meng He +2
Average Stretch Factor: How Low Does It Go?
Vida Dujmovic, Pat Morin, Michiel Smid
Memoryless Routing in Convex Subdivisions: Random Walks are Optimal
Dan Chen, Luc Devroye, Vida Dujmovic +1
EPG-representations with small grid-size
Therese Biedl, Martin Derka, Vida Dujmovic +1
Planar Visibility: Testing and Counting
Joachim Gudmundsson, Pat Morin
Layout of Graphs with Bounded Tree-Width
Vida Dujmovic, Pat Morin, David R. Wood
Algorithms for Marketing-Mix Optimization
Joachim Gudmundsson, Pat Morin, Michiel Smid
Spanners of Complete $k$-Partite Geometric Graphs
Prosenjit Bose, Paz Carmi, Mathieu Couture +3
Robust Geometric Spanners
Prosenjit Bose, Vida Dujmovic, Pat Morin +1
Simultaneous Diagonal Flips in Plane Triangulations
Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao +2
Towards Tight Bounds on Theta-Graphs
Prosenjit Bose, Jean-Lou De Carufel, Pat Morin +2
On Obstacle Numbers
Vida DujmoviÄ, Pat Morin
A polynomial bound for untangling geometric planar graphs
Prosenjit Bose, Vida Dujmovic, Ferran Hurtado +3
More Turán-Type Theorems for Triangles in Convex Point Sets
Boris Aronov, Vida DujmoviÄ, Pat Morin +2
The $θ_5$-graph is a spanner
Prosenjit Bose, Pat Morin, André van Renssen +1
The Price of Order
Prosenjit Bose, Pat Morin, André van Renssen
Encoding Arguments
Pat Morin, Wolfgang Mulzer, Tommy Reddad
A Characterization of the Degree Sequences of 2-Trees
Prosenjit Bose, Vida DujmoviÄ, Danny Krizanc +4
Range Mode and Range Median Queries on Lists and Trees
Danny Krizanc, Pat Morin, Michiel Smid
Improved Methods For Generating Quasi-Gray Codes
Dana Jansens, Prosenjit Bose, Paz Carmi +3
Queue Layouts of Graphs with Bounded Degree and Bounded Genus
Vida DujmoviÄ, Pat Morin, David R. Wood
Array Layouts for Comparison-Based Searching
Paul-Virak Khuong, Pat Morin
A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model
Evangelos Kranakis, Danny Krizanc, Pat Morin +2
Compatible Connectivity-Augmentation of Planar Disconnected Graphs
Greg Aloupis, Luis Barba, Paz Carmi +3
Near-Optimal $O(k)$-Robust Geometric Spanners
Prosenjit Bose, Paz Carmi, Vida Dujmovic +1
Distinct Distances in Graph Drawings
Paz Carmi, Vida DujmoviÄ, Pat Morin +1
The Fresh-Finger Property
John Howat, John Iacono, Pat Morin
Biased Range Trees
Vida Dujmovic, John Howat, Pat Morin
Encoding 3SUM
Sergio Cabello, Jean Cardinal, John Iacono +3
Odds-On Trees
Prosenjit Bose, Luc Devroye, Karim Douieb +3
Anagram-Free Chromatic Number is not Pathwidth-Bounded
Paz Carmi, Vida DujmoviÄ, Pat Morin
Spanning Trees in Multipartite Geometric Graphs
Ahmad Biniaz, Prosenjit Bose, David Eppstein +3
Notes on large angle crossing graphs
Vida Dujmovic, Joachim Gudmundsson, Pat Morin +1
Layered Separators in Minor-Closed Graph Classes with Applications
Vida DujmoviÄ, Pat Morin, David R. Wood
Orthogonal Tree Decompositions of Graphs
Vida DujmoviÄ, Gwenaël Joret, Pat Morin +2
Geodesic Obstacle Representation of Graphs
Prosenjit Bose, Paz Carmi, Vida Dujmovic +4
On the Average Number of Edges in Theta Graphs
Pat Morin, Sander Verdonschot
Visibility-Monotonic Polygon Deflation
Prosenjit Bose, Vida DujmoviÄ, Nima Hoda +1
Top-Down Skiplists
Luis Barba, Pat Morin
New Bounds for Facial Nonrepetitive Colouring
Prosenjit Bose, Vida DujmoviÄ, Pat Morin +1
Point Location in Disconnected Planar Subdivisions
Prosenjit Bose, Luc Devroye, Karim Douieb +3
Approximating Majority Depth
Dan Chen, Pat Morin
Crossings in Grid Drawings
Vida Dujmovic, Pat Morin, Adam Sheffer