@String{aap = {\emph{Advances in Applied Probability}}} @String{alg = {\emph{Algorithmica}}} @String{talg = {\emph{ACM Transactions on Algorithms}}} @String{jacm = {\emph{Journal of the ACM}}} @String{cgta = {\emph{Computational Geometry: Theory and Applications}}} @String{sicomp = {\emph{SIAM Journal on Computing}}} @String{cccg2010 = {\emph{CCCG~2010}}} @String{iwoca2010 = {\emph{IWOCA~2010}}} @String{ipl = {\emph{Information Processing Letters}}} @String{ton = {\emph{ACM/IEEE Transactions on Networking}}} @String{wn = {\emph{Wireless Networks}}} @String{towc = {\emph{IEEE Transactions on Wireless Communications}}} @String{cccg2012 = {The 24th Canadian Conference on Computational Geometry (CCCG~2012)}} @Misc{major2, author = {D. Chen and P. Morin}, title = {Approximating Majority Depth}, howpublished = {arXiv:1205.1524}, month = {May}, year = {2012}, note = {Submitted to }#cccg2012#{ in April 2012}, link = {\publink{arxiv}{http://arxiv.org/abs/1205.1524}} } @Misc{giant, author = {P. Bose and V. Dujmovi\'c and P. Morin and M. Smid}, title = {Robust Geometric Spanners}, howpublished = {arXiv:1204.4679}, month = {April}, year = {2012}, note = {Submitted to }#sicomp#{ in April 2012}, link = {\publink{arxiv}{http://arxiv.org/abs/1204.4679}} } @Misc{interference2, author = {L. Devroye and P. Morin}, title = {A Note on Interference in Random Point Sets}, howpublished = {arXiv:1202.5945}, month = {February}, year = {2012}, link = {\publink{arXiv}{http://arxiv.org/abs/1202.5945}}, note = {Submitted to }#ton#{ in March 2012 and immediately rejected. \newblock Submitted to }#towc#{ in March 2012 and immediately rejected. \newblock Submitted to }#wn#{ in April 2012}, link = {\publink{arXiv}{http://arxiv.org/abs/1202.5945}} } @InCollection{hashtables, author = {P. Morin}, title = {Hash Tables}, booktitle = {Handbook of Data Structures and Applications}, publisher = {CRC Press}, chapter = 9, editor = {Dinesh Mehta and Sartaj K. Sahni}, year = 2004, link = {\publink{web page}{http://www.amazon.com/exec/obidos/ASIN/1584884355/pricegrabbercom/103-2418854-3615067}} } @String{algorithmica = {\emph{Algorithmica}}} @String{aap = {\emph{Advances in Applied Probability}}} @String{jgaa = {\emph{Journal of Graph Algorithms and Applications}}} @String{beitrage = {\emph{Beitr\"age zur Algebra und Geometrie } (Contributions to Algebra and Geometry)}}} @String{cgta = {\emph{Computational Geometry: Theory and Applications}}} @String{cviu = {\emph{Computer Vision and Image Understanding}}} @String{dam = {\emph{Discrete Applied Mathematics}}} @String{dcg = {\emph{Discrete {\&} Computational Geometry}}} @String{geombinatorics = {\emph{Geombinatorics}}} @String{ipl = {\emph{Information Processing Letters}}} @String{ijcga = {\emph{International Journal of Computational Geometry and Applications}}} @String{joda = {\emph{Journal of Discrete Algorithms}}} @String{sicomp = {\emph{SIAM Journal on Computing}}} @String{tcs = {\emph{Theoretical Computer Science}}} @String{tocs = {\emph{Theory of Computing Systems}}} @String{wn = {\emph{Wireless Networks}}} @String{njc = {\emph{Nordic Journal of Computing}}} @String{jgt = {\emph{Journal of Graph Theory}}} @String{stco = {\emph{Statistics and Computing}}} @String{ejc = {\emph{Electronic Journal of Combinatorics}}} @String{dmtcs = {\emph{Discrete Mathematics {\&} Theoretical Computer Science}}} @String{talg = {\emph{ACM Transactions on Algorithms}}} @String{jog = {\emph{Journal of Geometry}}} @String{cjtcs = {\emph{Chicago Journal of Theoretical Computer Science}}} @String{joco = {\emph{Journal of Combinatorial Optimization}}} @article{oja, author = {D. Chen and O. Devillers and J. Iacono and P. Morin}, title = {{O}ja Medians and Centers of Gravity}, journal = cgta, note = {Accepted in March 2012. Special issue of selected papers from \emph{CCCG~2010}}, link = {\publink{pdf}{xxx/ojacgta.pdf}} } @Article{transmitters-dummy, title = {Coverage with {$k$}-Transmitters in the Presence of Obstacles}, author = {B. Ballinger and N. Benbernou and P. Bose and M. Damian and E. D. Demaine and V. Dujmovi\'c and R. Flatland and F. Hurtado and J. Iacono and A. Lubiw and P. Morin and V. Sacrist\'an and D. Souvaine and R. Uehara}, journal = joco, note = {Accepted in February 2012.\newblock Preliminary version appears in \emph{Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA2010)}, pages Part II: 1-15, 2010}, link = {\publink{pdf}{xxx/transmitters.pdf}} } @Article{tkapprox, title = {Absolute approximation of {T}ukey depth: Theory and experiments}, author = {D. Chen and P. Morin and U. Wagner}, journal = cgta, note = {Accepted in January 2012. Special issue on Geometric Optimization}, link = {\publink{pdf}{xxx/tkapprox.pdf}} } @Article{loglogd, author = {P. Bose and K. Dou\"\i eb and V. Dujmovi\'c and J. Howat and P. Morin}, title = {Fast Local Searches and Updates in Bounded Universes}, journal = cgta, note = {Accepted in December 2011. Special issue of selected papers from \emph{CCCG~2010}}, link = {\publink{pdf}{xxx/loglogd.pdf}} } @Article{succprop, author = {P. Bose and J. Howat and P. Morin}, title = {A Distribution-Sensitive Dictionary with Low Space Overhead}, journal = joda, note = {Accepted in November 2011. \newblock Preliminary version appears in \emph{Proceedings of the 16th International Workshop on Algorithms and Data Structures (WADS 2009)}, \emph{LNCS}, pages 110-118. Springer, 2009.}, history = {Submitted to }#ipl#{, March 2010; rejected in July 2010.}, link = {\publink{pdf}{ds/succprop-joda.pdf}} } @Article{skiplifts, author = {P. Bose and K. Dou\"\i eb and P. Morin}, title = {Skip Lifts: A Probabilistic Alternative to Red-Black Trees}, journal = joda, note = {Accepted, pending minor revisions, in September 2011. \newblock Special issue of selected papers from the \emph{International Workshop on Combinatorial Algorithms (IWOCA~2010)}}, link = {\publink{pdf}{xxx/skiplifts.pdf}} } @Article{entropy2, author = {S. Collette and V. Dujmovi\'c and J. Iacono and S. Langerman and P. Morin}, title = {Entropy, Triangulation, and Point Location in Planar Subdivisions}, journal = talg, history = "Submitted to " # jacm # ", in January 2009, and immediately rejected.\\ Submitted to " # talg, note = {Accepted in August 2011}, link = {\publink{pdf}{ds/entropy2-talg.pdf} \publink{arXiv}{http://arxiv.org/abs/0901.1908}} } @Article{succinctpl, author = {P. Bose and E. Chen and M. He and A. Maheshwari and P. Morin}, title = {Succinct Geometric Indexes Supporting Point Location}, journal = talg, volume = {8}, number = {2}, month = {April}, year = {2012}, link = {\publink{arXiv}{http://arxiv.org/abs/0805.4147}}, link = {\publink{pdf}{ds/pointlocation.pdf}}, note = {Preliminary version appeared in \emph{Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)}, pages 635-644, 2009} } @Article{convobl, author = {D. Chen and V. Dujmovi\'c and L. Devroye and P. Morin}, title = {Memoryless Routing in Convex Subdivisions: Random Walks are Optimal}, journal = cgta, volume = {45}, number = {4}, pages = {178--185}, year = {2012}, note = {Preliminary version appears at EuroCG~2010}, link = {\publink{pdf}{online/convobl-cgta.pdf}\publink{arXiv}{http://arxiv.org/abs/0911.2484}}, } @Article{rangetrees, author = {V. Dujmovi\'c and J. Howat and P. Morin}, title = {Biased range trees}, journal = algorithmica, link = {\publink{arXiv}{http://arxiv.org/abs/0806.2707}}, volume = {62}, number = {1}, pages = {21--37}, year = {2012}, note = {Preliminary version appeared in \emph{Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)}, pages 486--495, 2009.}, history = {Submitted to \emph{SIAM Journal on Computing}, July 2008.\\ Rejected from \emph{SICOMP}, February 2009.\\ Submitted to \emph{Discrete {\&} Computational Geometry}, February 2009.\\ Rejected from \emph{DCG}, August 2009.\\ Submitted to \emph{Algorithmica}, November 2009.}, } @Article{lac, author = {V. Dujmovi\'c and J. Gudmundsson and P. Morin and T. Wolle}, title = {Notes on Large Angle Crossing Graphs}, journal = cjtcs, year = {2011}, note = {Special issue of selected papers from \emph{Computing: The Australasian Theory Symposium (CATS~2010)}}, link = {\publink{website}{http://cjtcs.cs.uchicago.edu/}\publink{arXiv}{http://arxiv.org/abs/0908.3545}} } @Article{impdel, author = {K. Buchin and M. L\"offler and W. Mulzer and P. Morin}, title = {Delaunay Triangulation of Imprecise Points Simplified and Extended}, journal = algorithmica, volume = {61}, number = {3}, pages = {674--693}, year = {2011}, note = {Preliminary version appears in \emph{Proceedings of the 16th International Workshop on Algorithms and Data Structures (WADS 2009)}, LNCS. Springer, 2009.}, link = {\publink{springerlink}{http://dx.doi.org/10.1007/s00453-010-9430-0}} } @Article{rendezvous, author = {E. Kranakis and D. Krizanc and P. Morin}, title = {Randomized Rendez-Vous with Limited Memory}, journal = talg, volume = 7, number = 3, month = {July}, pages = {34:1--34:12}, year = {2011}, note = {Preliminary version appears in \emph{Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN2008)}, pages 605-616, 2008.}, link = {\publink{pdf}{xxx/rendezvous.pdf}} } @Article{winternitz, author = {P. Bose and P. Carmi and F. Hurtado and P. Morin}, title = {A Generalized {W}internitz Theorem}, journal = jog, volume = 100, issue = 1, year = 2011, pages = {29--35}, link = {\publink{pdf}{depth/winternitz-jog.pdf}} } @Article{pricing, author = {J. Gudmundsson and P. Morin and M. Smid}, title = {Algorithms for Marketing-Mix Optimization}, journal = algorithmica, volume = {60}, number = {4}, year = {2011}, link = {\publink{pdf}{all/pricing-algorithmica.pdf} \publink{arXiv}{http://arxiv.org/abs/0903.0308}}, history = {Submitted to (and rejected from) \emph{WADS 2009}.\\ Submitted to \emph{ISAAC 2009} and withdrawn. \\ Submitted to } #algorithmica, } @Article{sigma, author = {P. Bose and S. Collette and S. Langerman and A. Maheshwari and P. Morin and M. Smid}, title = {Sigma-Local Graphs}, journal = joda, volume = {8}, pages = {15--23}, year = {2010}, link = {\publink{pdf}{cg/sigma-submitted.pdf}} } @Article{proxdegree, author = {L. Devroye and J. Gudmundsson and P. Morin}, title = {On the Expected Maximum Degree of {G}abriel and {Y}ao Graphs}, journal = aap, volume = {41}, number = {4}, pages = {1123--1140}, year = {2009}, link = {\publink{arXiv}{http://arxiv.org/abs/0905.3584}} } @Article{untangling, author = {P. Bose and V. Dujmovi\'c and F. Hurtado and S. Langerman and P. Morin and D. R. Wood}, title = {A polynomial bound for untangling geometric planar graphs}, journal = dcg, volume = {42}, number = {2}, year = {2009}, pages = {570--585}, note = {Preliminary version appeared at \emph{Topological and Geometric Graph Theory (TGGT~2008)}}, link = {\publink{arXiv}{http://arxiv.org/abs/0710.1641}} } @Article{clamshell3d, author = {P. Bose and P. Morin and M. Smid and S. Wuhrer}, title = {Clamshell Casting}, journal = algorithmica, volume = {55}, number = {4}, pages = {666--702}, year = {2009}, note = {Preliminary version appears in \emph{Proceedings of CAD'07}}, link = {\publink{pdf}{casting/clamshell3d-tr.pdf}}, } @Article{pixels, author = {P. Bose and V. Dujmovi\'c and F. Hurtado and P. Morin}, title = {Connectivity-Preserving Transformations of Binary Images}, journal = cviu, volume = {113}, number = {10}, pages = {1027--1104}, year = {2009}, month = {October}, link = {\publink{pdf}{pr/pixels-cviu.pdf}}, } note = {Special issue dedicated to the memory of Azriel~Rosenfeld} @Article{outliers2, author = {R. Atanassov and P. Bose and M. Couture and A. Maheshwari and P. Morin and M. Paquette and M. Smid and S. Wuhrer}, title = {Algorithms for Optimal Outlier Removal}, journal = joda, volume = {7}, pages = {239--248}, year = {2009}, link = {\publink{pdf}{depth/outliers2-jda.pdf}} } @Article{clamshell2d, author = {P. Bose and P. Morin and M. Smid and S. Wuhrer}, title = {Rotationally Monotone Polygons}, journal = cgta, volume = {42}, year = {2009}, pages = {471--483}, booktitle = {Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG~2006)}, link = {\publink{pdf}{casting/clamshell2d-cgta.pdf}}, note = {See also \cite{clamshell2d_cccg}} } @Article{wedges, author = {J. Erickson and F. Hurtado and P. Morin}, title = {Centerpoint Theorems for Wedges}, journal = dmtcs, volume = {11}, number = {1}, pages = {45--54}, year = {2009}, link = {\publink{pdf}{depth/wedge-submitted.pdf}\publink{note}{depth/wedge-note.txt}}, } @Article{bispanners, author = {P. Bose and P. Carmi and M. Couture and A. Maheshwari and P. Morin and M. Smid}, title = {Spanners of Complete {$k$}-Partite Geometric Graphs}, journal = sicomp, volume = {38}, number = {5}, pages = {1803--1820}, year = {2009}, note = {Preliminary version appears in \emph{Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN2008)}, 2008.}, link = {\publink{pdf}{spanner/bispanners-submitted.pdf}} } @Article{twotrees, author = {P. Bose and V. Dujmovi\'c and D. Krizanc and S. Langerman and P. Morin and D. R. Wood and S. Wuhrer}, title = {A Characterization of the Degree Sequences of 2-Trees}, journal = jgt, pages = {191--209}, volume = {58}, number = {3}, year = {2008}, note = {Preliminary version appears in \emph{Proceedings of ANALCO~2007}}, link = {\publink{pdf}{gt/2trees.pdf}\publink{arXiv}{http://arxiv.org/abs/cs/0605011}}, } @Article{bloom, author = {P. Bose and H. Guo and E. Kranakis and A. Maheshwari and P. Morin and J. Morrison and M. Smid and Y. Tang}, title = {On the False-Positive Rate of {B}loom Filters}, journal = ipl, volume = {108}, year = {2008}, pages = {210--213}, link = {\publink{ps.gz}{ds/bloom-ipl.ps.gz} \publink{pdf}{ds/bloom-ipl.pdf}}, } @Article{distnum, author = {P. Carmi and V. Dujmovi\'c and P. Morin and D. R. Wood}, title = {Distinct Distances in Graph Drawings}, journal = ejc, volume = 15, number = {R107}, month = {August}, year = 2008, link = {\publink{pdf}{gd/distnum-submitted.pdf}} } @Article{ostukey, author = {D. Bremner and D. Chen and J. Iacono and S. Langerman and P. Morin}, title = {Output-Sensitive Algorithms for {T}ukey Depth and Related Problems}, journal = stco, volume = {18}, number = {3}, pages = {259--266}, month = {September}, year = {2008}, link = {\publink{pdf}{depth/tukey-sac.pdf}} } @Article{zonoidd, author = {P. Morin}, title = {An Optimal Randomized Algorithm for {$d$}-Variate Zonoid Depth}, journal = cgta, volume = {39}, number = {3}, pages = {229--235}, year = {2008}, link = {\publink{pdf}{depth/zonoidd-cgta.pdf}}, } @Article{detour2, author = {P. K. Agarwal and R. Klein and C. Knauer and S. Langerman and P. Morin and M. Sharir and M. Soss}, title = {Computing the Detour and Spanning Ratio of Paths, Trees and Cycles in 2D and 3D}, journal = dcg, volume = {39}, number = {1}, pages = {17--37}, year = {2008}, note = {Related results are contained in Conference Paper~\cite{detour}}, link = {\publink{ps.gz}{spanner/detour2-submitted.ps.gz} \publink{pdf}{spanner/detour2-submitted.pdf}}, } @Article{realizing, author = {E. D. Demaine and J. Erickson and D. Krizanc and H. Meijer and P. Morin and M. Overmars and S. Whitesides}, title = {Realizing Partitions Respecting Full and Partial Order Information}, journal = joda, volume = {6}, year = {2008}, pages = {51--58}, link = {\publink{ps.gz}{music/realizing-joda.ps.gz} \publink{pdf}{music/realizing-joda.pdf}}, note = {Preliminary version appears in \emph{Proceedings of the Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)}, pages 105-114, 2005} } @Article{band, author = {G. Aloupis and E. D. Demaine and S. Langerman and P. Morin and J. O'Rourke and I. Streinu and G. T. Toussaint}, title = {Unfolding Polyhedral Bands}, journal = cgta, volume = {39}, number = {1}, pages = {30--42}, year = {2008}, link = {\publink{pdf}{linkage/band-cgta.pdf}}, note = {Special issue of selected papers from \emph{The 16th Canadian Conference on Computational Geometry (CCCG 2004), 2004.}}, } @Article{zonoid, author = {H. Gopala and P. Morin}, title = {Algorithms for Bivariate Zonoid Depth}, journal = cgta, volume = {39}, number = {1}, pages = {2--13}, year = {2008}, note = {Special issue of selected papers from the \emph{16th Canadian Conference on Computational Geometry (CCCG~2004)}}, link = {\publink{pdf}{depth/zonoid-cgta.pdf}}, } @Article{flips2, author = {G. Aloupis and P. Bose and P. Morin}, journal = algorithmica, title = {Reconfiguring Triangulations with Edge Flips and Point Moves}, volume = {47}, number = {4}, pages = {367--378}, year = {2007}, note = {Special issue of selected papers from the \emph{12th International Symposium on Graph Drawing}, pages~1--11, volume 3383 of LNCS, Springer-Verlag}, link = {\publink{ps.gz}{gd/flips2-submitted.ps.gz} \publink{pdf}{gd/flips2-submitted.pdf}}, } @Article{geoham, author = {P. Bose and E. D. Demaine and F. Hurtado and S. Langerman and J. Iacono and P. Morin}, journal = dcg, title = {Geodesic Ham-Sandwich Cuts}, volume = {37}, number = {3}, pages = {325--330}, year = {2007}, note = {Preliminary version appears in \emph{Proceedings of the Twentieth ACM Symposium on Computational Geometry (SoCG 2004)}, pages 1-9. ACM Press, 2004.}, link = {\publink{ps.gz}{cutting/ham-dcg.ps.gz} \publink{pdf}{cutting/ham-dcg.pdf} \publink{citeseer}{http://citeseer.ist.psu.edu/648174.html}}, } @Article{insitu2, author = {P. Bose and A. Maheshwari and P. Morin and J. Morrison and M. Smid and J. Vahrenhold}, title = {Space-Efficient Geometric Divide-and-Conquer Algorithms}, journal = cgta, volume = {37}, number = {3}, year = {2007}, pages = {209--227}, note = {Preliminary version appears in \emph{Proceedings of the 20th European Workshop on Computational Geometry (EWCG~2004)}}, link = {\publink{ps.gz}{insitu/insitu2-cgta.ps.gz} \publink{pdf}{insitu/insitu2-cgta.pdf}} } @Article{flipping, author = {P. Bose and J. Czyzowicz and Z. Gao and P. Morin and D. R. Wood}, title = {Simultaneous Diagonal Flips in Plane Triangulations}, journal = jgt, volume = {54}, number = {4}, pages = {307--330}, year = {2006}, note = {Preliminary version appears in \emph{Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms}, pages 212-221, 2006}, link = {\publink{pdf}{gt/simflips.pdf}} } @Article{rmmq, author = {D. Krizanc and P. Morin and M. Smid}, title = {Range Mode and Range Median Queries on Lists and Trees}, journal = njc, volume = {12}, pages = {1--17}, year = {2005}, note = {Preliminary version appears in \emph{Proceedings of the Fourteenth Annual International Symposium on Algorithms and Computation (ISAAC 2003)}, volume 1906 of LNCS, pages 517-526, 2003}, link = {\publink{pdf}{ds/rmq-njc.pdf} \publink{ps.gz}{ds/rmq-njc.ps.gz}} } @Article{boundary, author = {D. Bremner and E. D. Demaine and J. Erickson and J. Iacono and S. Langerman and P. Morin and G. T. Toussaint}, title = {Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries}, journal = dcg, volume = {33}, number = {4}, pages = {593--604}, year = {2005}, note = {Preliminary version appears in \emph{Proceedings of the Workshop on Algorithms and Data Structures (WADS~2003)}, pages~451--461, LNCS, 2748, Springer-Verlag, 2003}, link = {\publink{pdf}{pr/boundary-dcg.pdf} \publink{ps.gz}{pr/boundary-dcg.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/593554.html}}, } @Article{covering, author = {S. Langerman and P. Morin}, title = {Covering things with things}, journal = dcg, volume = {33}, number = {4}, pages = {717--729}, year = {2005}, note = {Preliminary version appears in \emph{Proceedings of the 10th European Symposium on Algorithms (ESA~2002)}, pages~662--673, LNCS~2461, Springer-Verlag, 2002}, link = {\publink{pdf}{fpt/covering-dcg.pdf} \publink{ps.gz}{fpt/covering-dcg.ps.gz} \publink{correction}{fpt/covering-note.txt}}, copy = {\svcopy} } @Article{treewidth, author = {V. Dujmovi\'c and P. Morin and D. R. Wood}, title = {Layout of Graphs with Bounded Tree-Width}, journal = sicomp, volume = {34}, number = {3}, pages = {553--579}, year = {2005}, link = {\publink{pdf}{gd/treewidth-sicomp.pdf} \publink{ps.gz}{gd/treewidth-sicomp.ps.gz}}, } @Article{onebend, author = {P. Morin and D. R. Wood}, title = {Three-Dimensional 1-Bend Graph Drawings}, journal = jgaa, volume = {8}, number = {3}, year = {2004}, pages = {357--366}, note = {Preliminary version appears in \emph{Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG~2004)}}, link = {\publink{ps.gz}{gd/onebend-jgaa.ps.gz} \publink{pdf}{gd/onebend-jgaa.pdf} \publink{slides}{gd/onebend-slides/}}, } @Article{maxedges3d, author = {P. Bose and J. Czyzowicz and P. Morin and D. R. Wood}, title = {The Maximum Number of Edges in a Three-Dimensional Grid-Drawing}, journal = jgaa, volume = {8}, number = {1}, pages = {21--26}, year = {2004}, link = {\publink{pdf}{gd/volume-jgaa.pdf} \publink{ps.gz}{gd/volume-jgaa.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/575206.html}}, note = {Preliminary version appeared at \emph{The 19th European Workshop on Computational Geometry (EuroCG~2003)}}, } @Article{carpentry, author = {P. Morin and J. Morrison}, title = {The geometry of carpentry and joinery}, journal = dam, volume = {144}, number = {3}, pages = {374--380}, year = {2004}, note = {Special issue of selected papers from \emph{Fun with Algorithms 2 (FUN~2001)}}, link = {\publink{pdf}{cutting/carpentry-dam.pdf} \publink{ps.gz}{cutting/carpentry-dam.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/482777.html}} } @Article{routing_competitive, author = {P. Bose and P. Morin}, title = {Competitive Online Routing in Geometric Graphs}, journal = tcs, volume = {324}, number = {2--3}, pages = {273--288}, year = {2004}, note = {Special Issue: In Memoriam, Steve Seiden. Preliminary version appears in \emph{Proceedings of the VIIIth International Colloquium on Structural Information and Communication Complexity (SIROCCO~2001)}, pages~35--44, 2001}, link = {\publink{pdf}{online/ear-tcs.pdf} \publink{ps.gz}{online/ear-tcs.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/bose01competitive.html}} } @Article{2disks, author = {P. Bose and P. Morin and A. Vigneron}, title = {Packing two disks into a polygonal environment}, journal = joda, volume = {2}, number = {3}, pages = {373--380}, year = {2004}, note = {Preliminary version appears in \emph{Proceedings of The 7th Annual International Computing and Combinatorics Conference (COCOON~2001)}, pages~142--149, LNCS~2108, Springer-Verlag, 2001}, link = {\publink{pdf}{packing/disks-joda.pdf} \publink{ps.gz}{packing/disks-joda.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/bose01packing.html}}, } @Article{routing_triangs, author = {P. Bose and P. Morin}, title = {Online routing in triangulations}, journal = sicomp, volume = {33}, number = {4}, pages = {937--951}, year = {2004}, note = {Preliminary version appears in \emph{Proceedings of the Tenth International Symposium on Algorithms and Computation (ISAAC'99)}, pages~113--122, LNCS~1741, Springer-Verlag, 1999}, link = {\publink{pdf}{online/triangs-siamjc.pdf} \publink{ps.gz}{online/triangs-siamjc.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/bose99online.html} \publink{source code}{online/routing.tgz}}, } @Article{robinhood, author = {L. Devroye and P. Morin and A. Viola}, title = {On worst case {R}obin-{H}ood hashing}, journal = sicomp, volume = {33}, number = {4}, pages = {923--936}, year = {2004}, link = {\publink{pdf}{hashing/robinhood-siamjc.pdf} \publink{ps.gz}{hashing/robinhood-siamjc.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/580911.html}} } @Article{insitu, author = {H. Br\"onnimann and J. Iacono and J. Katajainen and P. Morin and J. Morrison and G. T. Toussaint}, title = {Space-efficient planar convex hull algorithms}, journal = tcs, volume = {321}, number = {1}, pages = {25--40}, year = {2004}, note = {Special issue of selected papers from \emph{Latin American Theoretical INformatics (LATIN 2002)}}, link = {\publink{pdf}{insitu/insitu-tcs.pdf} \publink{ps.gz}{insitu/insitu-tcs.ps.gz} \publink{source}{insitu/insitu-src.tgz}}, } @Article{otheta, author = {P. Bose and J. Gudmundsson and P. Morin}, title = {Ordered theta graphs}, journal = cgta, volume = {28}, number = {1}, pages = {11--18}, year = {2004}, note = {Special issue of selected papers from \emph{The 14th Canadian Conference on Computational Geometry (CCCG~2002)}}, link = {\publink{ps.gz}{spanner/theta-cgta.ps.gz} \publink{pdf}{spanner/theta-cgta.pdf} \publink{citeseer}{http://citeseer.nj.nec.com/526852.html}} } @Article{quality, author = {P. Bose and P. Morin}, title = {Testing the Quality of Manufactured Disks and Balls}, journal = algorithmica, volume = {38}, number = {2}, pages = {161--177}, year = {2004}, note = {Special issue on Shape Algorithmics (Remco C. Veltkamp, editor)}, link = {\publink{pdf}{probing/probing-algorithmica.pdf} \publink{ps.gz}{probing/probing-algorithmica.ps.gz}}, } @Article{dotmaps, author = {M. de Berg and P. Bose and O. Cheong and P. Morin}, title = {On simplifying dot maps}, journal = cgta, volume = {27}, number = {1}, pages = {43--62}, year = {2004}, note = {Special issue of selected papers from the \emph{Xth European Conference on Computational Geometry (EuroCG~2002)}}, link = {\publink{pdf}{cartography/dotmaps-cgta.pdf} \publink{ps.gz}{cartography/dotmaps-cgta.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/deberg02simplifying.html}} } @Article{asymmetric, author = {P. Bose and D. Krizanc and S. Langerman and P. Morin}, title = {Asymmetric communication protocols via hotlink assignments}, journal = tocs, volume = {36}, number = {6}, pages = {655--661}, year = {2003}, note = {Special issue of selected papers from the \emph{IXth International Colloquium on Structural Information and Communication Complexity (SIROCCO~2002)}}, link = {\publink{pdf}{distrib/asymmetric-tocs.pdf} \publink{ps.gz}{distrib/asymmetric-tocs.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/508481.html}}, } @Article{tukey, author = {P. Bra\ss and L. Heinrich-Litan and P. Morin}, title = {Computing the Center of Area of a Convex Polygon}, journal = ijcga, volume = {13}, year = {2003}, pages = {439--445}, link = {\publink{pdf}{facility/center-ijcga.pdf} \publink{ps.gz}{facility/center-ijcga.ps.gz} \publink{slides}{facility/center/}} } @Article{grids, author = {P. Bose and M. van Kreveld and A. Maheshwari and P. Morin and J. Morrison}, title = {Translating a regular grid over a point set}, journal = cgta, volume = {25}, number = {1--2}, pages = {21--34}, year = {2003}, note = {Special issue of selected papers from the \emph{The 17th European Workshop on Computational Geometry (EuroCG~2001)}, 2001. Preliminary version appears in \emph{Proceedings of the 7th Annual Workshop on Algorithms and Data Structures (WADS~2001)}, pages~180--191, LNCS~2125, Springer-Verlag, 2001}, link = {\publink{pdf}{facility/placement-cgta.pdf} \publink{ps.gz}{facility/placement-cgta.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/538676.html}}, } @Article{cuckoo, author = {L. Devroye and P. Morin}, title = {Cuckoo hashing: Further analysis}, journal = ipl, volume = {86}, number = {4}, pages = {215--219}, year = 2003, link = {\publink{pdf}{hashing/cuckoo-ipl.pdf} \publink{ps.gz}{hashing/cuckoo-ipl.ps.gz} \publink{note}{hashing/cuckoo-note.txt}} } @Article{sums, author = {P. Bose and A. Maheshwari and P. Morin}, title = {Fast approximations for sums of distances, clustering and the {F}ermat-{W}eber problem}, journal = cgta, volume = {24}, number = {3}, pages = {135--146}, year = 2002, note = {Preliminary version appears in \emph{IX Encuentros de Geometr\'\i a Computacional (9EGC)}, 2001}, link = {\publink{pdf}{facility/objective-cgta.pdf} \publink{ps.gz}{facility/objective-cgta.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/508349.html}}, } @Article{traversal, author = {P. Bose and P. Morin}, title = {An improved algorithm for subdivision traversal without extra storage}, journal = ijcga, volume = 12, number = 4, pages = {297--308}, year = 2002, note = {Special issue of selected papers from the \emph{11th Annual International Symposium on Algorithms and Computation (ISAAC~2000)}}, link = {\publink{pdf}{gis/traversal-ijcga.pdf} \publink{ps.gz}{gis/traversal-ijcga.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/bose99improved.html} \publink{source code}{gis/traversal.tar.gz}} } @Article{routing_convex, author = {P. Bose and A. Brodnik and S. Carlsson and E. D. Demaine and R. Fleischer and A. L\'opez-Ortiz and P. Morin and J. I. Munro}, title = {Online routing in convex subdivisions}, journal = ijcga, year = 2002, volume = 12, number = 4, pages = {283--296}, note = {Special issue of selected papers from the \emph{11th Annual International Symposium on Algorithms and Computation (ISAAC~2000)}}, link = {\publink{pdf}{online/oblivious-ijcga.pdf} \publink{ps.gz}{online/oblivious-ijcga.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/bose00online.html}} } @Article{convexification, author = {J. A. Calvo and D. Krizanc and P. Morin and M. Soss and G. T. Toussaint}, title = {Convexifying polygons with simple projections}, journal = ipl, year = 2001, volume = 80, number = 2, pages = {81--86}, link = {\publink{pdf}{linkage/convexify3d-ipl.pdf} \publink{ps.gz}{linkage/convexify3d-ipl.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/calvo00convexifying.html}} } @Article{deflation, author = {T. Fevens and A. Hernandez, A. Mesa and P. Morin and M. Soss and G. T. Toussaint}, title = {Simple polygons with an infinite sequence of deflations}, journal = beitrage, year = 2001, volume = 42, number = 2, pages = {307--311}, link = {\publink{pdf}{linkage/deflation-beitrage.pdf} \publink{ps.gz}{linkage/deflation-beitrage.ps.gz}} } @Article{routing_adhoc, author = {P. Bose and P. Morin and I. Stojmenovi\'c and J. Urrutia}, title = {Routing with guaranteed delivery in \emph{ad hoc} wireless networks}, journal = wn, year = 2001, volume = 7, number = 6, pages = {609--616}, note = {Special issue of selected papers from the \emph{3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM'99)}}, link = {\publink{pdf}{online/unitgraphs-wn.pdf} \publink{ps.gz}{online/unitgraphs-wn.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/bose00routing.html} \publink{source code}{online/face-routing.tgz}} } @Article{flipturns, author = {H.-K. Ahn and P. Bose and J. Czyzowicz and N. Hanusse and E. Kranakis and P. Morin}, title = {Flipping your lid}, journal = geombinatorics, year = 2000, volume = {X}, number = 2, pages = {57--63}, note = {Preliminary version appears in \emph{Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG'00)}}, link = {\publink{pdf}{linkage/flipturn-geombinatorics.pdf} \publink{ps.gz}{linkage/flipturn-geombinatorics.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/ahn00flipping.html}} } @String{lncs = {Lecture Notes in Computer Science}} @String{analco07 = {Workshop on Analytic Algorithms {\&} Combinatorics (ANALCO07)}} @String{adhocnow04 = {Proceedings of the 3rd International Conference on AD-HOC Networks \& Wireless (ADHOC-NOW'04)}} @String{awoca05 = {Proceedings of the Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)}} @String{gd02 = {Proceedings of the 10th International Symposium on Graph Drawing (GD2002)}} @String{isaac98 = {Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98)}} @String{isaac03 = {Proceedings of the Fourteenth Annual International Symposium on Algorithms and Computation (ISAAC~2003)}} @String{socg04 = {Proceedings of the Twentieth ACM Symposium on Computational Geometry (SoCG~2004)}} @String{socg04 = {Proceedings of the Twentieth ACM Symposium on Computational Geometry (SoCG~2004)}} @String{socg2010 = {Proceedings of the Twenty-Sixth ACM Symposium on Computational Geometry (SoCG~2010)}} @String{stacs02 = {Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002)}} @String{stacs05 = {Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS~2005)}} @String{sirocco03 = {Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO~2003)}} @String{soda06 = {Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA~2006)}} @String{soda08 = {Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA~2008)}} @String{soda09 = {Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA~2009)}} @String{wads99 = {Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99)}} @String{wads09 = {Proceedings of the 16th International Workshop on Algorithms and Data Structures (WADS~2009)}} @String{acmsac98 = {Proceedings of the 1998 ACM Symposium on Applied Computing (SAC'98)}} @String{acmgis97 = {Proceedings of the 5th International Workshop on Advances in Geographic Information Systems (ACM-GIS'97)}} @String{sac96 = {Proceedings of the Third Annual Workshop on Selected Areas in Cryptography (SAC'96)}} @String{latin08 = {Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN2008)}} @String{cats2010= {Proceedings of Computing: The Australasian Theory Symposium (CATS 2010)}} @String{swat2010 = {Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT~2010)}} @String{iwoca2010 = {Proceedings of the 21st International Workshop on Combinatorial Algorithms}} @String{cocoa2010 = {The 4th Annual International Conference on Combinatorial Optimization and Applications}} @String{ipl = {\emph{Information Processing Letters}}} @String{cjtcs = {\emph{Chicago Journal of Theoretical Computer Science}}} @String{sicomp = {\emph{SIAM Journal on Computing}}} @String{cgta = {\emph{Computational Geometry: Theory and Applications}}} InProceedings{transmitters, title = {Coverage with {$k$}-Transmitters in the Presence of Obstacles}, author = {B. Ballinger and N. Benbernou and P. Bose and M. Damian and E. D. Demaine and V. Dujmovi\'c and R. Flatland and F. Hurtado and J. Iacono and A. Lubiw and P. Morin and V. Sacrist\'an and D. Souvaine and R. Uehara}, booktitle = cocoa2010, pages = {Part II: 1--15}, year = {2010}, link = {\publink{pdf}{xxx/transmitters.pdf}} } InProceedings{skiplifts, author = {P. Bose and K. Dou\"\i eb and P. Morin}, title = {Skip Lifts: A Probabilistic Alternative to Red-Black Trees}, booktitle = iwoca2010, year = {2010}, link = {\publink{pdf}{xxx/skiplifts.pdf}} } Misc{loglogd, author = {P. Bose and K. Dou\"\i eb and V. Dujmovi\'c and J. Howat and P. Morin}, title = {Fast Local Searches and Updates in Bounded Universes}, booktitle = cccg2010, year = {2010}, note = {Invited to special issue of }#cgta#{ for CCCG~2010}, link = {\publink{pdf}{xxx/loglogd.pdf}} } @InProceedings{counters, author = {P. Bose and P. Carmi and D. Jansens and A. Maheshwari and M. Smid}, title = {Improved Methods for Generating Quasi-{G}ray Codes}, booktitle = swat2010, year = {2010}, publink = {ds/counters-submitted.pdf} } @InProceedings{viscover, author = {J. Gudmundsson and P. Morin}, title = {Planar Visibility: Testing and Counting}, booktitle = socg2010, year = {2010}, note = {Submitted to }#sicomp#{ in January 2010; rejected in July 2010.}, link = {\publink{arXiv}{http://arxiv.org/abs/1001.2734}} } InProceedings{lac, author = {V. Dujmovi\'c and J. Gudmundsson and P. Morin and T. Wolle}, title = {Notes on Large Angle Crossing Graphs}, booktitle = cats2010, year = {2010}, note = {Submitted to }#cjtcs#{, March 2010}, link = {\publink{arXiv}{http://arxiv.org/abs/0908.3545}} } InProceedings{succprop, author = {P. Bose and J. Howat and P. Morin}, title = {A Distribution-Sensitive Dictionary with Low Space Overhead}, booktitle = wads09, series = {LNCS}, publisher = {Springer}, pages = {110--118}, year = 2009, note = {Submitted to }#ipl#{, March 2010; rejected in July 2010.}, link = {\publink{pdf}{ds/succprop-submitted.pdf}} } @InProceedings{succorth, author = {P. Bose and M. He and A. Maheshwari and P. Morin}, title = {Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing}, booktitle = wads09, series = {LNCS}, publisher = {Springer}, pages = {98--109}, year = 2009, note = {Submitted to }# cgta #{ in June 2010; rejected in February 2011}, link = {\publink{pdf}{ds/succortho-submitted.pdf}} } InProceedings{impdel, author = {K. Buchin and M. L\"offler and W. Mulzer and P. Morin}, title = {Delaunay Triangulation of Imprecise Points Simplified and Extended}, booktitle = wads09, series = {LNCS}, publisher = {Springer}, year = 2009, note = {Submitted to \emph{Algorithmica}, November 2009}, link = {\publink{pdf}{ds/impdel-submitted.pdf}} } InProceedings{rangetrees, author = {V. Dujmovi\'c and J. Howat and P. Morin}, title = {Biased range trees}, booktitle = soda09, year = {2009}, pages = {486--495}, link = {\publink{arXiv}{http://arxiv.org/abs/0806.2707}}, note = {Preliminary version appeared in \emph{Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)}, pages 486--495, 2009.} history = {Submitted to \emph{SIAM Journal on Computing}, July 2008.\\ Rejected from \emph{SICOMP}, February 2009.\\ Submitted to \emph{Discrete {\&} Computational Geometry}, February 2009.\\ Rejected from \emph{DCG}, August 2009.\\ Submitted to \emph{Algorithmica}, November 2009.}, } InProceedings{succinctpl, author = {P. Bose and E. Chen and M. He and A. Maheshwari and P. Morin}, title = {Succinct Geometric Indexes Supporting Point Location}, booktitle = soda09, pages = {635--644}, year = {2009}, link = {\publink{arXiv}{http://arxiv.org/abs/0805.4147}}, note = {Submitted to \emph{ACM Transactions on Algorithms}, March 2009} } InProceedings{rendezvous, author = {E. Kranakis and D. Krizanc and P. Morin}, title = {Randomized Rendez-Vous with Limited Memory}, booktitle = latin08, year = 2008, pages = {605--616}, note = {Submitted to \emph{Random Structures and Algorithms}, July 2008, and immediately rejected. \ Submitted to \emph{ACM Transactions on Algorithms}, July 2008.}, link = {\publink{pdf}{distrib/rendezvous-submitted.pdf}} } Article{bispanners, author = {P. Bose and P. Carmi and M. Couture and A. Maheshwari and P. Morin and M. Smid}, title = {Spanners of Complete {$k$}-Partite Geometric Graphs}, booktitle = latin08, year = 2008, note = {Submitted to SIAM Journal on Computing, November 2007}, link = {\publink{pdf}{spanner/bispanners-submitted.pdf}} } @InProceedings{entropy, author = {S. Collette and V. Dujmovi\'c and J. Iacono and S. Langerman and P. Morin}, title = {Distribution-Sensitive Point Location in Convex Subdivisions}, booktitle = soda08, pages = {912--921}, year = {2008}, note = {Submitted to \emph{Journal of the ACM} in November 2006; rejected in August 2007.\\ Submitted to \emph{SIAM Journal on Computing} in August 2007; rejected in May 2008.}, link = {\publink{pdf}{ds/entropy-submitted.pdf}}, note2 = {Theoretical results have now been subsumed by Ref.~\cite{entropy2}}, } InProceedings{twotrees, author = {P. Bose and V. Dujmovi\'c and D. Krizanc and S. Langerman and P. Morin and D. R. Wood and S. Wuhrer}, title = {A Characterization of the Degree Sequences of 2-Trees}, booktitle = analco07, link = {\publink{arXiv}{http://arxiv.org/abs/cs/0605011}}, note = {Submitted to \emph{Journal of Graph Theory}, July 2006} } InProceedings{flipping, author = {P. Bose and J. Czyzowicz and Z. Gao and P. Morin and D. R. Wood}, title = {Simultaneous Diagonal Flips in Plane Triangulations}, booktitle = soda06, pages = {212--221}, year = 2006 } @InProceedings{rmq2, author = {P. Bose and E. Kranakis and P. Morin and Y. Tang}, title = {Approximate Range Mode and Range Median Queries}, booktitle = stacs05, pages = {377--388}, publisher = {Springer-Verlag}, volume = {3404}, series = lncs, copy = {\svcopy}, link = {\publink{pdf}{ds/rmq2-stacs.pdf}}, year = 2005 } @InProceedings{gps, author = {M. Barbeau and E. Kranakis and D. Krizanc and P. Morin}, title = {Improving Distance Based Geographic Location Techniques in Sensor Networks}, booktitle = adhocnow04, year = 2004, pages = {197--210}, link = {\publink{ps.gz}{online/gps-adhocnow.ps.gz} \publink{pdf}{online/gps-adhocnow.pdf}} } InProceedings{geoham, author = {P. Bose and E. D. Demaine and F. Hurtado and S. Langerman and J. Iacono and P. Morin}, title = {Geodesic Ham-Sandwich Cuts}, booktitle = socg04, pages = {1--9}, year = 2004, publisher = {ACM Press}, link = {\publink{ps.gz}{cutting/ham-socg.ps.gz} \publink{pdf}{cutting/ham-socg.pdf} \publink{slides}{cutting/ham-slides/} \publink{citeseer}{http://citeseer.ist.psu.edu/648174.html}}, copy = {\acmcopy} } @InProceedings{streaming, author = {P. Bose and E. Kranakis and P. Morin and Y. Tang}, title = {Bounds for Frequency Estimation of Packet Streams}, booktitle = sirocco03, year = 2003, pages = {33--42}, link = {\publink{pdf}{traffic/streaming-sirocco.pdf} \publink{ps.gz}{traffic/streaming-sirocco.ps.gz}} } @InProceedings{straight3d, author = {V. Dujmovi\'c and P. Morin and D. R. Wood}, title = {Pathwidth and 3-dimensional straight-line grid drawings of graphs}, booktitle = gd02, series = lncs, publisher = {Springer-Verlag}, pages = {42--53}, year = 2002, volume = {2528}, link = {\publink{pdf}{gd/straight3d-gd.pdf} \publink{ps.gz}{gd/straight3d-gd.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/537505.html}}, copy = {\svcopy} } @InProceedings{detour, author = {S. Langerman and P. Morin and M. Soss}, title = {Computing the maximum detour and spanning ratio of planar paths, trees and cycles}, booktitle = stacs02, pages = {250--261}, year = 2002, volume = 2285, series = lncs, publisher = {Springer-Verlag}, note = {Extended abstract appears at \emph{11th Fall Workshop on Computational Geometry}, 2001}, link = {\publink{pdf}{spanner/detour-stacs.pdf} \publink{ps.gz}{spanner/detour-stacs.ps.gz}}, copy = {\svcopy}, link = {\publink{pdf}{spanner/detour-stacs.pdf} \publink{ps.gz}{spanner/detour-stacs.ps.gz}} } @InProceedings{balls, author = {P. Bose and P. Morin}, title = {Testing the quality of manufactured balls}, booktitle = wads99, pages = {145--156}, year = 1999, volume = 1663, series = lncs, publisher = {Springer-Verlag}, link = {\publink{pdf}{probing/balls-wads.pdf} \publink{ps.gz}{probing/balls-wads.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/340008.html}}, copy = {\svcopy} } @InProceedings{disks, author = {P. Bose and P. Morin}, title = {Testing the quality of manufactured disks and cylinders}, booktitle = isaac98, pages = {129--138}, year = 1998, volume = 1533, series = lncs, publisher = {Springer-Verlag}, link = {\publink{pdf}{probing/disks-isaac.pdf} \publink{ps.gz}{probing/disks-isaac.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/bose98testing.html}}, copy = {\svcopy} } @InProceedings{hcgm, author = {P. Morin}, title = {Coarse grained parallel computing on heterogeneous systems}, booktitle = acmsac98, pages = {628--634}, year = 1998, publisher = {ACM Press}, link = {\publink{short pdf}{parallel/hcgm-sac.pdf} \publink{short ps.gz}{parallel/hcgm-sac.ps.gz} \publink{long pdf}{parallel/hcgm-long.pdf} \publink{long ps.gz}{parallel/hcgm-long.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/morin98coarsegrained.html}}, copy = {\acmcopy} } @InProceedings{pm, author = {A. Maheshwari and P. Morin and J.-R. Sack}, title = {Progressive {TIN}s: Algorithms and applications}, booktitle = acmgis97, pages = {24--29}, year = 1997, publisher = {ACM Press}, link = {\publink{short pdf}{gis/pm-acmgis.pdf} \publink{short ps.gz}{gis/pm-acmgis.ps.gz} \publink{long pdf}{gis/pm-long.pdf} \publink{long ps.gz}{gis/pm-long.ps.gz}}, copy = {\acmcopy} } @InProceedings{aardvark, author = {P. Morin}, title = {Provably secure and efficient block ciphers}, booktitle = sac96, pages = {30--37}, year = 1996, link = {\publink{pdf}{crypto/aardvark-sac.pdf} \publink{ps.gz}{crypto/aardvark-sac.ps.gz}} } @String{cgta = {\emph{Computational Geometry: Theory and Applications}}} @String{ijcga = {\emph{International Journal of Computational Geometry and Applications}}} @String{eurocg2010 = {Proceedings of the 26th European Workshop on Computational Geometry (EuroCG~2010)}} @String{cccg2010 = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG~2010)}} @String{cccg2011 = {Proceedings of the 23nd Canadian Conference on Computational Geometry (CCCG~2011)}} @InProceedings{majority, title = {Algorithms for Bivariate Majority Depth}, author = {D. Chen and P. Morin}, booktitle = cccg2011, year = 2011, pages = {425--430}, link = {\publink{cccg version}{http://cccg.ca/proceedings/2011/papers/paper69.pdf}} } @Misc{interference, title = {A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model}, author = {E. Kranakis and D. Krizanc and P. Morin and L. Narayanan and L. Stacho}, journal = ipl, howpublished = {arXiv:1007.2120}, month = {July}, year = 2010, xnote = {Accepted, pending minor revisions, in October 2010}, link = {\publink{arXiv}{http://arxiv.org/abs/1007.2120}} } @InProceedings{chimneys, author = {D. Charlton and E. D. Demaine and M. L. Demaine and V. Dujmovi\'c and P. Morin and R. Uehara}, title = {Ghost Chimneys}, booktitle = cccg2010, year = {2010}, note = {Submitted to }#ijcga#{in April 2001. Revised in December 2011 and again in March 2012.}, link = {\publink{pdf}{xxx/chimneys.pdf}} } InProceedings{oja, author = {D. Chen and O. Devillers and J. Iacono and P. Morin}, title = {{O}ja Medians and Centers of Gravity}, booktitle = cccg2010, year = {2010}, note = {Invited to special issue of }#cgta#{ for CCCG~2010}, link = {\publink{short pdf}{xxx/oja.pdf}\publink{full pdf}{xxx/ojacgta.pdf}} } @Misc{oddson, author = {P. Bose and L. Devroye and K. Dou\"\i eb and V. Dujmovi\'c and J. King and P. Morin}, title = {Odds-on trees}, howpublished = {arXiv:1002.1092}, month = {February}, year = {2010}, link = {\publink{arXiv}{http://arxiv.org/abs/1002.1092} \publink{note}{ds/odds-on.txt}} } @Misc{blobs, author = {P. Bose and L. Devroye and K. Dou\"\i eb and V. Dujmovi\'c and J. King and P. Morin}, title = {Point Location in Disconnected Planar Subdivisions}, howpublished = {arXiv:1001.2763}, month = {January}, year = {2010}, link = {\publink{arXiv}{http://arxiv.org/abs/1001.2763}} } @TechReport{diet2, title = {Putting your data structure on a diet}, author = {H. Br\"onnimann and J. Katajainen and P. Morin}, institution = {Performance Engineering Laboratory, DIKU}, number = {CPH-STL-2007-1}, year = {2007}, link = {\publink{pdf}{http://www.cphstl.dk/Report/Diet/diet.pdf}} } @InProceedings{outliers, author = {R. Atanassov and P. Morin and S. Wuhrer}, title = {Removing Outliers to Minimize Area and Perimeter}, booktitle = {Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG~2006)}, year = 2006, link = {\publink{pdf}{depth/outliers-cccg.pdf} \publink{tech report}{http://www.scs.carleton.ca/research/tech_reports/2006/abstract.php?TR_FILE=2006/tr-06-07_0013.xml}}, } @TechReport{clamshell3dtr, author = {P. Bose and P. Morin and M. Smid and S. Wuhrer}, title = {Rotational Clamshell Casting in Three Dimensions}, institution = {Carleton University School of Computer Science}, year = 2006, link = {\publink{pdf}{casting/clamshell3d-tr.pdf}}, number = {TR-06-04}, } @InProceedings{clamshell2d_cccg, author = {P. Bose and P. Morin and M. Smid and S. Wuhrer}, title = {Rotational Clamshell Casting in Two Dimensions}, booktitle = {Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG~2006)}, year = 2006, link = {\publink{pdf}{casting/clamshell2d-tr.pdf}}, } InProceedings{band, author = {G. Aloupis and E. D. Demaine and S. Langerman and P. Morin and J. O'Rourke and I. Streinu and G. T. Toussaint}, title = {Unfolding Polyhedral Bands}, booktitle = {Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG~2004)}, link = {\publink{ps.gz}{linkage/band-cccg.ps.gz} \publink{pdf}{linkage/band-cccg.pdf}}, year = 2004, note = {Full version submitted to \emph{Computational Geometry: Theory and Applications}, November 2004 (Special issue for CCCG~2004)} } @InProceedings{minimalist, author = {P. Bose and L. Devroye and P. Morin}, title = {Succinct Data Structures for Approximating Convex Functions with Applications}, booktitle = {Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG~2002)}, year = 2003, publisher = {Springer-Verlag}, series = {LNCS}, volume = {2866}, pages = {97--107}, link = {\publink{short pdf}{facility/curves-jcdcg.pdf} \publink{short ps.gz}{facility/curves-jcdcg.ps.gz} \publink{long pdf}{facility/curves-full.pdf} \publink{long ps.gz}{facility/curves-full.ps.gz}}, copy = {\svcopy}, note = {Submitted to \emph{Journal of Discrete Algorithms}, January 2005} } @TechReport{diet, author = {P. Morin}, title = {Putting your Dictionary on a Diet}, institution = {Carleton University School of Computer Science}, year = 2002, month = nov, number = {TR-02-07}, link = {\publink{pdf}{ds/tinydict-tr.pdf} \publink{ps.gz}{ds/tinydict-tr.ps.gz}} } @InProceedings{covering_basic, author = {S. Langerman and P. Morin}, title = {Covering points with lines (abstract)}, booktitle = {11th Fall Workshop on Computational Geometry}, year = 2001, note = {Results are included in Journal Paper~\cite{covering}}, link = {\publink{pdf}{fpt/linecover-fw.pdf} \publink{ps.gz}{fpt/linecover-fw.ps.gz}} } @PhdThesis{phdthesis, author = {P. Morin}, title = {Online Routing in Geometric Graphs}, school = {School of Computer Science, Carleton University}, year = 2001, month = {January}, link = {\publink{pdf}{theses/phd/phd.pdf} \publink{ps}{theses/phd/phd.ps}} } @InProceedings{framework, author = {A. Maheshwari and P. Morin and J.-R. Sack}, title = {A framework for multiresolution modeling}, booktitle = {Proceedings of the Workshop on Multiresolution Representation of 3D Geometry for Progressive Transmission}, year = 1998, link = {\publink{ps.gz}{misc/multires.ps.gz}} } @MastersThesis{mcsthesis, author = {P. Morin}, title = {Two topics in applied algorithmics}, school = {School of Computer Science, Carleton University}, year = 1998, link = {\publink{ps.gz}{theses/mcs/thesis-mcs.ps.gz} \publink{citeseer}{http://citeseer.nj.nec.com/morin98two.html}} } @InProceedings{tomlin, author = {D. Dubrule and P. Morin and J.-R. Sack}, title = {A parallel cartographic modelling system: Design, implementation and performance}, booktitle = {GIS'97 Proceedings}, pages = {16--20}, year = 1997, link = {\publink{scanned pdf}{cartography/tomlin.pdf}} } @TechReport{ecash, author = {P. Morin}, title = {Secure non-interactive electronic cash}, institution = {School of Computer Science, Carleton University}, year = 1996, number = {TR-96-06}, link = {\publink{ps.gz}{http://www.scs.carleton.ca/publications/tech_reports/1996/TR-96-06.ps.gz}} } @Article{bm03, author = {P. Bose and P. Morin}, title = {Guest Editors' Introduction}, journal = {Algorithmica}, volume = {42}, number = {1}, pages = {1--2}, year = 2005, note = {Special issue of selected papers from ISAAC~2002} } @Article{bm04, author = {P. Bose and P. Morin}, title = {Guest Editors' Introduction}, journal = {Theory of Computing Systems}, volume = {38}, issue = {3}, pages = {251}, year = 2005, note = {Special issue of selected papers from ISAAC 2002} } @Proceedings{bm02, title = {Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2002)}, year = 2002, editor = {P. Bose and P. Morin}, series = {LNCS}, volume = 2815, publisher = {Springer-Verlag}, link = {\publink{online}{http://link.springer.de/link/service/series/0558/tocs/t2518.htm}} } @Misc{talk11, title = {Interference!}, howpublished = {BIRS: Models of Sparse Graphs and Network Algorithms}, address = {Banff, Canada}, month = {February}, note = {\publink{pdf}{talks/interference-talk.pdf} \publink{xoj}{talks/interference-talk.xoj}}, year = 2011 } @Misc{talk09, title = {On the Expected Maximum Degree in {Y}ao Graphs}, howpublished = {Dagstuhl Seminar on Geometric Networks, Metric Space Embeddings and Spatial Data Mining}, address = {Dagstuhl, Germany}, month = {November}, year = 2009 } @Misc{talk08b, title = {Randomized Algorithms {I}, {II}, and {III}}, howpublished = {New Zealand Institute of Mathematics and its Applications. Programme in Algorithmics}, address = {Christchurch, New Zealand}, month = {December}, note = {\publink{pdf i}{randalg/rand-alg-1.pdf} \publink{pdf ii}{randalg/rand-alg-2.pdf} \publink{pdf iii}{randalg/rand-alg-3.pdf}}, year = 2008 } @Misc{talk08a, title = {Distribution-Sensitive Point Location}, howpublished = {Sydney Theory Day}, address = {Sydney, Australia}, month = {May}, year = 2008 } @Misc{talk07a, title = {Algorithms for Zonoids}, howpublished = {East Coast Combinatorial Conference (ECCC~2007)}, month = {April}, year = 2007 } @Misc{talk06c, title = {Disctribution-Sensitive Point Location in Convex Subdivisions}, howpublished = {Algorithms Seminar, McGill University}, month = {December}, year = 2006 } @Misc{talk06b, title = {An Optimal Algorithm for $d$-Variate Zonoid Depth}, howpublished = {Algorithms Seminar, Universit\'e Libre de Bruxelles}, month = {October}, year = 2006 } @Misc{talk06a, title = {Recent results on data depth and outlier removal in 2D}, howpublished = {Radcliffe Institute Seminar on Computational Aspects of Statistical Data Depth Analysis, Cambridge, MA, USA}, month = {July}, year = 2006 } @Misc{talk05b, title = {Centerpoint theorems for wedges}, howpublished = {Japan Workshop on Discrete and Computational Geometry, Kanezawa, Japan}, month = {May}, year = 2005 } @Misc{talk05a, title = {Realizing partitions respecting full and partial order information}, howpublished = {UPC Computational Geometry Seminar}, month = {May}, year = 2005 } @Misc{talk03b, title = {Computing the Center of Area of a Convex Polygon}, howpublished = {DIMACS Workshop on Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications}, month = {May}, year = 2003 } @Misc{talk03a, title = {Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries}, howpublished = {MITACS Workshop on Facility Location, Ottawa, Canada}, month = {May}, year = 2003 } @Misc{talk02, title = {Computing the Center of Area of a Convex Polygon}, howpublished = {MITACS Workshop on Facility Location, Vancouver, Canada}, month = {June}, year = 2002 } @Misc{talk01, title = {Two recent results on flipping polygons}, howpublished = {Special Session on Physical Knotting and Unknotting, AMS Spring Western Section Meeting, Las Vegas, Nevada, USA}, month = {April}, year = 2001 } @Misc{talkX, title = {Classifying adult content on the Internet}, howpublished = {School of Computer Science, McGill University}, month = {June}, year = 2001 } @Misc{talkP, title = {Online routing in geometric networks}, howpublished = {SEMNET (SEMinar on NETworks), Department of Mathematics, Carleton University}, month = {November}, year = 2001 } @Misc{talkQ, title = {Progressive {TIN}s: Algorithms and Applications}, howpublished = {Max-Planck-Institut f\"ur Informatik}, month = {August}, year = 1997 } @Misc{talkF, title = {Course-grained parallel computing on heterogeneous systems}, howpublished = {Oberseminar Bl\"omer/Meyer auf der Heide: Theoretische Informatik 2. Universit\"at-GH Paderborn}, month = {May}, year = 1997 } @Misc{talkJ, title = {Performance evaluation with {P}arasol}, howpublished = {Real-Time and Distributed Systems Seminar. Department of Systems and Computer Engineering, Carleton University}, month = {October}, year = 1996 }