@String{aap = {\emph{Advances in Applied Probability}}}
@String{alg = {\emph{Algorithmica}}}
@String{gac = {\emph{Graphs and Combinatorics}}}
@String{talg = {\emph{ACM Transactions on Algorithms}}}
@String{jacm = {\emph{Journal of the ACM}}}
@String{cgta = {\emph{Computational Geometry: Theory and Applications}}}
@String{dcg = {\emph{Discrete {\&} Computational Geometry}}}
@String{sicomp = {\emph{SIAM Journal on Computing}}}
@String{sidma = {\emph{SIAM Journal on Discrete Mathematics}}}
@String{cccg2010 = {\emph{CCCG~2010}}}
@String{iwoca2010 = {\emph{IWOCA~2010}}}
@String{ipl = {\emph{Information Processing Letters}}}
@String{jgt = {\emph{Journal of Graph Theory}}}
@String{ton = {\emph{ACM/IEEE Transactions on Networking}}}
@String{wn = {\emph{Wireless Networks}}}
@String{towc = {\emph{IEEE Transactions on Wireless Communications}}}
@String{cdm = {\emph{Contributions to Discrete Mathematics}}}
@String{ejc = {\emph{Electronic Journal of Combinatorics}}}
@string{jea = {\emph{ACM Journal of Experimental Algorithmics}}}
@string{tcs = {\emph{Threoretical Computer Science}}}
@string{acmcsurv = {\emph{ACM Computing Surveys}}}
@string{annalap= {\emph{Annals of Applied Probability}}}
@string{sosa2018={\emph{Symposium on Simplicity in Algorithms}}}
@misc{queue-best,
author = {V. Dujmovi\'c and G. Joret and P. Micek and P. Morin
and T. Ueckerdt and D. R. Wood},
title = {Planar Graphs Have Bounded Queue-Number},
howpublished = {Submitted to \emph{FOCS~2019}},
note = {\arxiv{1904.04791}}
}
@misc{queue,
author = {V. Dujmovi\'c and P. Morin and D. R. Wood},
title = {Queue Layouts of Graphs with Bounded Degree and Bounded Genus},
note = {\arxiv{1901.05594}},
}
@misc{robust2,
author = {P. Bose and P. Carmi and V. Dujmovi\'c and P. Morin},
title = {Near-Optimal ${O(k)}$-Robust Geometric Spanners},
note = {\arxiv{1812.09913}},
}
@misc{layeredpathwidth,
author = {V. Dujmovi\'c and D. Eppstein and G. Joret and P. Morin and D. R. Wood},
title = {Minor-Closed Graph Classes with Bounded Layered Pathwidth},
howpublished = {Submitted to }#sidma#{ in October 2018},
link = {\arxiv{1810.08314}}
}
@Book{ods_python,
author = {P. Morin},
title = {Open Data Structures (in Pseudocode)},
publisher = {Web},
year = 2014,
note = {A freely-available open content textbook},
link = {\publink{website}{http://opendatastructures.org}}
}
@Book{ods_java,
author = {P. Morin},
title = {Open Data Structures: An Introduction},
publisher = {Athabasca University Press},
address = {Edmonton},
year = 2013,
note = {Also freely available as {\em Open Data Structures
(in Java)} at \url{opendatastructures.org}},
link = {\publink{website}{http://opendatastructures.org}},
}
@Book{ods_cpp,
author = {P. Morin},
title = {Open Data Structures (in C++)},
publisher = {Web},
year = 2012,
note = {A freely-available open content textbook},
link = {\publink{website}{http://opendatastructures.org}}
}
@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 = {Algorithmica}}
@String{acmcsurv = {ACM Computing Surveys}}
@String{aap = {Advances in Applied Probability}}
@String{jea = {ACM Journal of Experimental Algorithmics}}
@String{jgaa = {Journal of Graph Algorithms and Applications}}
@String{beitrage = {Beitr\"age zur Algebra und Geometrie
(Contributions to Algebra and Geometry)}}}
@String{cdm = {Contributions to Discrete Mathematics}}
@String{cgta = {Computational Geometry: Theory and Applications}}
@String{cviu = {Computer Vision and Image Understanding}}
@String{dam = {Discrete Applied Mathematics}}
@String{dcg = {Discrete {\&} Computational Geometry}}
@String{geombinatorics = {Geombinatorics}}
@String{ipl = {Information Processing Letters}}
@String{ijcga = {International Journal of Computational Geometry
and Applications}}
@String{joda = {Journal of Discrete Algorithms}}
@String{sicomp = {SIAM Journal on Computing}}
@String{tcs = {Theoretical Computer Science}}
@String{tocs = {Theory of Computing Systems}}
@String{wn = {Wireless Networks}}
@String{njc = {Nordic Journal of Computing}}
@String{jgt = {Journal of Graph Theory}}
@String{stco = {Statistics and Computing}}
@String{ejc = {Electronic Journal of Combinatorics}}
@String{dmtcs = {Discrete Mathematics {\&} Theoretical Computer Science}}
@String{talg = {ACM Transactions on Algorithms}}
@String{jog = {Journal of Geometry}}
@String{cjtcs = {Chicago Journal of Theoretical Computer Science}}
@String{joco = {Journal of Combinatorial Optimization}}
@String{socg2013 = {\emph{Proceedings of the Twenty-Ninth ACM Symposium on
Computational Geometry (SoCG~2013)}}}
@string{wg2013 = {\emph{Proceedings of the 39th International Workshop on
Graph-Theoretic Concepts in Computer Science (WG~2013)}}}
@String{latin14 = {Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN2014)}}
@String{ojac = {Online Journal of Analytic Combinatorics}}
@String{jctb = {Journal of Combinatorial Theory, Series B}}
@String{gac = {Graphs and Combinatorics}}
@String{sidma = {SIAM Journal on Discrete Mathematics}}
@string{rsa={Random Structures \& Algorithms}}
@Article{corrigendum,
author = {V. Dujmovi\'c and G. Joret and P. Morin and S. Norin and D. R. Wood},
title = {Corrigendum to ``{O}rthogonal Tree Decompositions of Graphs''},
journal = sidma,
volume = 32,
number = 4,
pages = {3003--3004},
year = {2018},
history = {Accepted, pending revisions, in October 2017},
link = {\doi{10.1137/18M1214196}}
}
@Article{turantype,
author = {B. Aronov and V. Dujmovi\'c and P. Morin and A. Ooms and L. F. S. Xavier da Silveira},
title = {More {T}ur\'an-Type Theorems for Triangles in Convex Point Sets},
journal = ejc,
volume = 26,
number = 1,
year = 2019,
note = {P1.8 (26 pages)},
xnote = {Accepted in September 2018},
history = {Revision submitted to }#ejc#{ in September 2018.\newblock
Submitted to }#ejc#{ in August 2017.\newblock
Submitted to }#dcg#{ in June 2017 and rejected in July 2017},
link = {\publink{journal version}{https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p8} \arxiv{1706.10193}}
}
@Article{alantree,
author = {L. Devroye and V. Dujmovi\'c and A. Frieze and
A. Mehrabian and P. Morin and B. Reed},
title = {Notes on Growing a Tree in a Graph},
journal = rsa,
note = {First published: 18 December, 2018},
history = {Submitted to }#rsa#{ in November 2017.\newblock
Submitted to }#annalap#{ in June 2017 and rejected
in October 2017},
link = {\arxiv{1707.00083} \doi{10.1002/rsa.20828}}
}
@Article{orthogonaltreedecomp,
author = {V. Dujmovi\'c and G. Joret and P. Morin and S. Norin and D. R. Wood},
title = {Orthogonal Tree Decompositions of Graphs},
journal = sidma,
volume = 32,
number = 2,
pages = {839--863},
year = {2018},
history = {Accepted, pending revisions, in October 2017},
link = {\arxiv{1701.05639} \doi{10.1137/17M1112637}}
}
@Article{interference2,
author = {L. Devroye and P. Morin},
title = {A Note on Interference in Random Networks},
journal = cgta,
volume = 67,
year = 2018,
pages = {2--10},
booktitle = cccg2012,
note = {Preliminary version appeared at CCCG 2012.},
history = {Submitted to }#cgta#{ in May 2016. \newblock
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 and rejected
in August 2012},
link = {\arxiv{1202.5945}\doi{10.1016/j.comgeo.2017.10.006}}
}
@Article{layeredseparators,
author = {V. Dujmovi\'c and P. Morin and D. R. Wood},
title = {Layered Separators in Minor-Closed Graph Classes with Applications},
journal = jctb,
volume = 127,
pages = {111-147},
year = 2017,
note = {Preliminary version appeared at FOCS~2013},
link = {\arxiv{1306.1595}
\doi{10.1016/j.jctb.2017.05.006}}
}
@Article{bichromaticmst,
author = {A. Biniaz and P. Bose and D. Eppstein and A. Maheshwari and P. Morin and M. Smid},
title = {Spanning Trees in Multipartite Geometric Graphs},
journal = algorithmica,
volume = 80,
number = 11,
pages = {3177--3191},
month = {November},
year = {2018},
history = {Submitted to } # alg # { in November 2016.
Accepted, pending minor revisions, in April 2017},
link = {\arxiv{1611.01661}
\doi{10.1007/s00453-017-0375-4}},
}
@Article{encoding,
author = {P. Morin and W. Mulzer and T. Reddad},
title = {Encoding Arguments},
journal = acmcsurv,
volume = 50,
number = 3,
pages = {46:1--36},
year = 2017,
history = {Submitted to } #acmcsurv# { in March 2016.\newblock
Revised in September 2016.},
link = {\arxiv{1603.08777}
\doi{10.1145/3084288}}
}
@Article{avgtheta,
author = {P. Morin and S. Verdonschot},
title = {On the Average Number of Edges in Theta Graphs},
journal = ojac,
note = {Accepted in July 2016.\newblock
Preliminary version appeared at \emph{ANALCO~2014}},
link = {\arxiv{1304.3402}
\publink{mathematica code}{spanner/avgtheta.html}}
}
@Article{facial,
author = {P. Bose and V. Dujmovi\'c and P. Morin and \lucas},
title = {New Bounds for Facial Nonrepetitive Colouring},
journal = gac,
volume = 33,
number = 4,
pages = {817--832},
year = {2017},
history = {Submitted to } # jgt # { in April 2016 and rejected in May 2016.\newblock
Submitted to } # gac # { in December 2016.},
link = {\arxiv{1604.01282}\doi{10.1007/s00373-017-1816-1}}
}
@Article{arraylayouts,
author = {P.-V. Khuong and P. Morin},
title = {Array Layouts for Comparison-Based Searching},
journal = jea,
volume = {22},
number = {1},
note = {Article No. 1.3 (39 pages)},
year = {2017},
history = {Submitted to } #jea# { in September 2015.
\newblock Revised in May 2016.
\newblock Accepted in January 2017},
link = {\arxiv{1509.05053}\doi{10.1145/3053370}
\publink{github}{https://github.com/patmorin/arraylayout}}
}
@Article{biased-pred,
author = {P. Bose and R. Fagerberg and J. Howat and P. Morin},
title = {Biased Predecessor Search},
journal = algorithmica,
volume = {76},
number = {4},
pages = {1097--1105},
year = {2016},
note = {Preliminary version appeared at \emph{LATIN~2014}},
publink = {\doi{10.1007/s00453-016-0146-7}}
}
@Article{tighttheta,
author = {P. Bose and J.-L. De Carufel and P. Morin and A. van Renssen and S. Verdonschot},
title = {Towards Tight Bounds on Theta-Graphs: More is not
always better},
journal = tcs,
volume = 616,
pages = {70--93},
year = {2016},
link = {\arxiv{1404.6233}\doi{10.1016/j.tcs.2015.12.017}}
}
@Article{priceoforder,
author = {P. Bose and P. Morin and A. van Renssen},
title = {The Price of Order},
journal = ijcga,
volume = {26},
number = {3},
pages = {135--149},
year = {2016},
note = {Preliminary version appeared at \emph{ISAAC~2014}},
link = {\arxiv{1602.00399a}\doi{10.1142/S0218195916600013}}
}
booktitle = isaac14,
pages = {313--325},
year = {2014}
@Article{augmentation,
author = {G. Aloupis and L. Barba and P. Carmi and V. Dujmovi\'c and F. Frati
and P. Morin},
title = {Compatible Connectivity Augmentation of Planar Disconnected Graphs},
journal = dcg,
volume = 54,
number = 2,
pages = {459--480},
year = {2015},
note = {Preliminary version appeared at \emph{SODA~2015}},
link = {\arxiv{1408.2436}\doi{10.1007/s00454-015-9716-8}}
}
@Article{monovis,
author = {P. Bose and V. Dujmovi\'c and N. Hoda and P. Morin},
title = {Visibility-Monotonic Polygon Deflation},
journal = cdm,
volume = 10,
number = 1,
pages = {1--21},
year = {2015},
note = {Preliminary version appears in \emph{Proceedings of CCCG 2012}},
link = {\publink{PID}{http://hdl.handle.net/10515/sy5z02zr6}\arxiv{1206.1982}}
}
@Article{onobstacles,
author = {V. Dujmovi\'c and P. Morin},
title = {On Obstacle Numbers},
journal = ejc,
volume = 22,
number = 3,
year = {2015},
note = {P3.1 (7 pages)},
link = {\publink{journal version}{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p1}\arxiv{1308.4321}}
}
@Article{avgstretch,
author = {V. Dujmovi\'c and P. Morin and M. Smid},
title = {Average Stretch Factor: How Low Does It Go?},
journal = dcg,
volume = 53,
number = 2,
year = 2015,
pages = {296--326},
link = {\arxiv{1305.4170}\doi{10.1007/s00454-015-9663-4}}
}
@Article{theta5,
author = {P. Bose and P. Morin and A. van Renssen and S. Verdonschot},
title = {The {$\Theta_5$} Graph is a Spanner},
journal = cgta,
volume = {48},
number = {2},
pages = {108--119},
year = {2015},
note = {Preliminary version appears in } # wg2013,
link = {\arxiv{1212.0570}\doi{10.1016/j.comgeo.2012.04.004}}
}
@Article{3dcrossings,
author = {V. Dujmovi\'c and P. Morin and A. Sheffer},
title = {Crossings in Grid Drawings},
journal = ejc,
volume = 21,
number = 1,
year = 2014,
note = {P1.41 (18 pages)},
link = {\publink{journal version}{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p41}
\arxiv{1301.0303}}
}
@Article{giant,
author = {P. Bose and V. Dujmovi\'c and P. Morin and M. Smid},
title = {Robust Geometric Spanners},
journal = sicomp,
volume = {42},
number = {4},
pages = {1720--1736},
year = {2013},
note = {Preliminary version appears in } # socg2013 # {, ACM Press, 2013},
history = {Submitted to }#sicomp#{ in April 2012\newblock
Accepted, pending minor revisions, in February 2013.},
link = {\arxiv{1204.4679}\doi{10.1137/120874473}}
}
@article{major2,
author = {D. Chen and P. Morin},
title = {Approximating Majority Depth},
journal = cgta,
volume = {46},
number = {9},
pages = {1059--1064},
year = {2013},
note = {Special issue of selected papers from \emph{CCCG~2012}},
link = {\arxiv{1205.1524}\doi{10.1016/j.comgeo.2013.06.005}}
}
@Article{tkapprox,
title = {Absolute approximation of {T}ukey depth:
Theory and experiments},
author = {D. Chen and P. Morin and U. Wagner},
journal = cgta,
volume = 46,
number = 5,
pages = {566--573},
year = {2013},
note = {Special issue on Geometric Optimization},
link = {\publink{pdf}{xxx/tkapprox.pdf}\doi{10.1016/j.comgeo.2012.03.001}}
}
@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,
volume = {25},
number = {2},
pages = {208--233},
year = {2013},
month = {March},
note = {Preliminary version appears in \emph{Proceedings of the
4th Annual International Conference on Combinatorial
Optimization and Applications (COCOA2010)}, Part
II: 1-15, 2010},
link = {\publink{pdf}{xxx/transmitters.pdf}\doi{10.1007/s10878-012-9475-x}}
}
@article{oja,
author = {D. Chen and O. Devillers and J. Iacono and S. Langerman and P. Morin},
title = {{O}ja Centers and Centers of Gravity},
journal = cgta,
volume = {46},
number = {2},
pages = {140--147},
year = {2013},
note = {Special issue of selected papers
from \emph{CCCG~2010}},
link = {\publink{pdf}{xxx/ojacgta.pdf}\doi{10.1016/j.comgeo.2012.04.004}}
}
@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,
volume = {46},
number = {2},
pages = {181--189},
year = {2013},
note = {Special issue of selected papers from \emph{CCCG~2010}},
link = {\publink{pdf}{xxx/loglogd.pdf}\doi{10.1016/j.comgeo.2012.01.002}}
}
@Article{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},
journal = ijcga,
volume = 22,
number = 3,
pages = {207--214},
year = {2012},
note = {Preliminary version appears in \emph{Proceedings of CCCG 2010}},
history = {Submitted to }#ijcga#{in April 2001. Revised in December 2011 and again in March 2012.},
link = {\publink{pdf}{xxx/chimneys.pdf}\doi{10.1142/S0218195912500057}}
}
@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,
volume = {8},
number = {3},
pages = {29:1--29:18},
year = {2012},
history = "Submitted to " # jacm # ", in January 2009,
and immediately rejected.\\
Submitted to " # talg,
link = {\arxiv{0901.1908}\doi{10.1145/2229163.2229173}}
}
@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,
volume = 14,
pages = {13--20},
year = {2012},
note = {Special issue of selected papers from
the \emph{International Workshop on
Combinatorial Algorithms (IWOCA~2010)}},
link = {\publink{pdf}{xxx/skiplifts.pdf}\doi{10.1016/j.jda.2011.12.017}}
}
@Article{succprop,
author = {P. Bose and J. Howat and P. Morin},
title = {A Distribution-Sensitive Dictionary with Low Space Overhead},
journal = joda,
volume = 10,
pages = {140--145},
year = {2012},
note = {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}\doi{10.1016/j.jda.2011.11.003}}
}
@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},
pages = {10:1--10:26},
month = {April},
year = {2012},
link = {\arxiv{0805.4147}},
link = {\publink{pdf}{ds/pointlocation.pdf}\doi{https://doi.org/10.1145/2151171.2151173}},
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 = {\arxiv{0911.2484}\doi{10.1016/j.comgeo.2011.12.005}},
}
@Article{rangetrees,
author = {V. Dujmovi\'c and J. Howat and P. Morin},
title = {Biased range trees},
journal = algorithmica,
link = {\arxiv{0806.2707}\doi{10.1007/s00453-010-9440-y}},
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/}\arxiv{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}
\arxiv{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 = {\arxiv{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 = {\arxiv{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 = {\arxiv{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{analco2014 = {Proceeding of the Eleventh Workshop on Analytic
Algorithmics and Combinatorics (ANALCO~2014)}}
@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{gd2017 = {Proceedings of the 25th International Symposium on
Graph Drawing (GD2017)}}
@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{isaac14 = {Proceedings of the Twenty-Fifth Annual International
Symposium on Algorithms and Computation (ISAAC~2014)}}
@String{socg04 = {Proceedings of the Twentieth Symposium on
Computational Geometry (SoCG~2004)}}
@String{socg2010 = {Proceedings of the Twenty-Sixth Symposium on
Computational Geometry (SoCG~2010)}}
@String{socg2013 = {Proceedings of the Twenty-Ninth Symposium on
Computational Geometry (SoCG~2013)}}
@String{socg2018 = {Proceedings of the 34th Symposium on
Computational Geometry (SoCG~2018)}}
@String{socg2019 = {Proceedings of the 35th Symposium on
Computational Geometry (SoCG~2019)}}
@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{soda15 = {Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA~2015)}}
@String{soda19 = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA~2019)}}
@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{wg2013 = {Proceedings of the 39th International Workshop on
Graph-Theoretic Concepts in Computer Science (WG~2013)}}
@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{latin14 = {Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN2014)}}
@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}}}
@String{icalp2018={\emph{The 45th International Colloquium on Automata, Languages, and Programming (ICALP~2018)}}}
@String{wg2018={\emph{44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2018)}}}
@String{dcg={\emph{Discrete \& Computational Geometry}}}
@InProceedings{collsets,
author = {V. Dujmovi\'c and P. Morin},
title = {Dual Circumference and Collinear Sets},
booktitle = socg2019,
note = {\arxiv{1811.03427}},
year = {2019}
}
@InProceedings{freecoll,
author = {V. Dujmovi\'c and F. Frati and D. Gon\c{c}alves and P. Morin and G. Rote},
title = {Every Collinear Set is Free},
booktitle = soda19,
note = {Submitted to }#dcg#{ in November 2018},
link = {\arxiv{1811.03432}},
year = 2019
}
@InProceedings{anagram-free,
author = {P. Carmi and V. Dujmovi\'c and P. Morin},
title = {Anagram-Free Chromatic Number is not Pathwidth-Bounded},
booktitle = wg2018,
year = 2018,
history = {Submitted to }#ejc#{ in February 2018\newblock
Submitted to }#wg2018#{ in February 2018},
link = {\arxiv{1802.01646}}
}
@InProceedings{geodesic-obstacle,
author = {P. Bose and P. Carmi and V. Dujmovi\'c and S. Mehrabi
and F. Montecchiani and P. Morin and L. F. Schultz Xavier Da Silveira},
title = {Geodesic Obstacle Representation of Graphs},
booktitle = icalp2018,
pages = {23:1--23:13},
note = {Submitted to \emph{Electronic Journal of Combinatorics} in
May 2018 and rejected in November 2018},
link = {\arxiv{1803.03705}},
year = {2018}
}
@InProceedings{kclubs,
author = {A. K. Abu-Affash and P. Carmi and A. Maheshwari
and P. Morin and M. Smid and S. Smorodinsky},
title = {Approximating Maximum Diameter-Bounded Subgraph in
Unit Disk Graphs},
booktitle = socg2018,
link = {\publink{LIPIcs}{http://drops.dagstuhl.de/opus/volltexte/2018/8715/pdf/LIPIcs-SoCG-2018-2.pdf}},
year = {2018}
}
@InProceedings{epg,
author = {T. Biedl and M. Derka and V. Dujmovic and P. Morin},
title = {{EPG}-Representations with Small Grid-Size},
booktitle = gd2017,
pages = {184--196},
year = 2017,
link = {\arxiv{1708.09749}}
}
InProceedings{augmentation,
author = {G. Aloupis and L. Barba and P. Carmi and V. Dujmovi\'c and F. Frati
and P. Morin},
title = {Compatible Connectivity-Augmentation of Planar Disconnected Graphs},
booktitle = soda15,
pages = {1602--1615},
year = {2015},
link = {\publink{arxiv}{http://arxiv.org/abs/1408.2436}}
}
InProceedings{priceoforder,
author = {P. Bose and P. Morin and A. van Renssen},
title = {The Price of Order},
booktitle = isaac14,
pages = {313--325},
year = {2014}
}
InProceedings{biased-pred,
author = {P. Bose and R. Fagerberg and J. Howat and P. Morin},
title = {Biased Predecessor Search},
booktitle = latin14,
pages = {755--764},
publisher = {Springer},
year = {2014}
}
InProceedings{avgtheta,
author = {P. Morin and S. Verdonschot},
title = {On the Average Number of Edges in Theta Graphs},
howpublished = {arXiv:1304.3402},
booktitle = analco2014,
pages = {121--132},
year = 2014,
publisher = {SIAM},
link = {\publink{arxiv}{http://arxiv.org/abs/1304.3402}
\publink{mathematica code}{spanner/avgtheta.html}}
}
inproceedings{laysep,
author = {V. Dujmovi\'c and P. Morin and D. R. Wood},
title = {Layered Separators in Minor-Closed Families
with Applications},
booktitle = {Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS~2013)},
link = {\publink{arxiv}{http://arxiv.org/abs/1306.1595}}
}
inproceedings{theta5,
author = {P. Bose and P. Morin and A. van Renssen and S. Verdonschot},
title = {The Theta-5 Graph is a Spanner},
booktitle = wg2013,
link = {\publink{arxiv}{http://arxiv.org/abs/1212.0570}}
}
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{common,
author = {G. Aloupis and P. Bose and S. Collette and E. D. Demaine and M. L. Demaine
and K. Dou\"\i eb and V. Dujmovi\'c and J. Iacono and S. Langerman and P. Morin},
title = {Common Unfoldings of Polyominoes and Polycubes},
booktitle = {Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications},
year = {2010},
series = lncs,
volume = {7033},
pages = {44--54},
publisher = {Springer},
link = {\publink{pdf}{xxx/common.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},
pages = {224--235},
publink = {ds/counters-submitted.pdf},
link = {\publink{arxiv}{https://arxiv.org/abs/1010.0905}}
}
@InProceedings{viscover,
author = {J. Gudmundsson and P. Morin},
title = {Planar Visibility: Testing and Counting},
booktitle = socg2010,
year = {2010},
pages = {77--86},
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)}}
@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)}}
@String{cdm = {\emph{Contributions to Discrete Mathematics}}}
@string{annalap= {\emph{Annals of Applied Probability}}}
@string{sosa2018={\emph{Symposium on Simplicity in Algorithms}}}
@String{eurocg2019={Proceedings of EuroCG~2019}}
@InProceedings{encoding3sum,
author = {S. Cabello and J. Cardinal and J. Iacono and S. Langerman
and P. Morin and A. Ooms},
title = {Encoding {3SUM}},
booktitle = eurocg2019,
note = {\arxiv{1903.02645}},
year = {2019}
}
@Misc{chernoff,
author = {P. Morin and W. Mulzer},
title = {A Simple Proof of {C}hernoff's Bound},
note = {Submitted to }#sosa2018#{ in August 2017 and rejected in November 2017},
link = {\publink{pdf}{drafts/chernoff.pdf}}
}
@Misc{firstpassage,
author = {L. Devroye and A. Mehrabian and P. Morin},
title = {First-Passage Percolation Time on the Hypercube},
note = {Submitted to }#sosa2018#{ in August 2017 and rejected in November 2017},
link = {\publink{pdf}{drafts/foxtrot.pdf}}
}
@Misc{tictactoe,
author = {J. L. A. Hood and P. Morin},
title = {Tic Tac Toe},
note = {First Place: Graph Drawing Contest 2015 (Creative Topics: Tic Tac Toe)},
year = {2015},
link = {\publink{a1 pdf}{gd/tictactoe.pdf}\publink{text}{gd/tictactoe.txt}}
}
@Misc{todolists,
author = {L. Barba and P. Morin},
title = {Top-Down Skiplists},
note = {Submitted to \emph{Algorithmica} in May 2016. \newblock
Submitted to, and rejected from, \emph{SODA 2015}. \newblock
Submitted to, and rejected from, \emph{ALENEX 2015}.},
link = {\publink{arxiv}{http://arxiv.org/abs/1407.7917}}
}
@Misc{freshfinger,
author = {J. Howat and J. Iacono and P. Morin},
title = {The fresh-finger property},
howpublished = {arXiv:1302.6914},
history = {Submitted to, and rejected from, \emph{LATIN 2013}.\newblock
Submitted to, and rejected from, \emph{WADS 2013}.},
link = {\publink{arxiv}{http://arxiv.org/abs/1302.6914}}
}
@InProceedings{theta2vs4,
author = {P. Bose and J.-L. De Carufel and P. Morin and A. van Renssen and S. Verdonschot},
title = {Optimal Bounds on Theta-Graphs: More is Not Always Better},
booktitle = cccg2012,
year = {2012},
pages = {305--310},
link = {\publink{pdf}{spanner/theta2vs4-cccg.pdf}}}
}
InProceedings{monovis,
author = {P. Bose and V. Dujmovi\'c and N. Hoda and P. Morin},
title = {Visibility-Monotonic Polygon Deflation},
booktitle = cccg2012,
year = {2012},
pages = {13--18},
note = {Submitted to }#cdm#{ in June 2012},
link = {\publink{arxiv}{http://arxiv.org/abs/1206.1982}}
}
InProceedings{major2,
author = {D. Chen and P. Morin},
title = {Approximating Majority Depth},
booktitle = cccg2012,
year = {2012},
pages = {237--242},
note = {Invited to special issue of }#cgta#{ for CCCG~2012},
link = {\publink{arxiv}{http://arxiv.org/abs/1205.1524}}
}
InProceedings{interference2,
author = {L. Devroye and P. Morin},
title = {A Note on Interference in Random Point Sets},
booktitle = cccg2012,
year = {2012},
pages = {201--206},
link = {\publink{arXiv}{http://arxiv.org/abs/1202.5945}},
note = {Submitted to }#cgta#{ in May 2016. \newblock
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 and rejected
in August 2012},
link = {\publink{arXiv}{http://arxiv.org/abs/1202.5945}}
}
InProceedings{theta3,
author = {P. Bose and P. Morin and A. van Renssen and S. Verdonschot},
title = {},
booktitle = cccg2012,
year = {2012},
note = {},
}
@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}
in 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. Morin},
title = {Guest Editor's Introduction},
journal = {Algorithmica},
volume = {??},
number = {?},
pages = {1},
year = 2005,
note = {Special issue of selected papers from CCCG~2008},
}
@Article{cccg-special-issue,
author = {P. Morin},
title = {Guest Editor's Introduction},
journal = {Computational Geometry: Theory and Applications},
volume = 47,
number = 2,
pages = {295},
year = 2014,
note = {Special issue of selected papers from CCCG~2008}
}
@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{talk17a,
title = {Growing a Spanning Tree of a Graph},
howpublished = {IMPA Probability and Combinatorics Seminar},
address = {Rio de Janeiro, Brazil},
month = {February},
year = {2017},
}
@Misc{talk16b,
title = {Tur\'{a}n-Type Theorems for Triangles in Convex Point Sets},
howpublished = {Shonan-Village Meeting on Geometric Optimization},
address = {Shonan Village, Japan},
month = {May},
year = {2016},
}
@Misc{talk16a,
title = {Tur\'{a}n-Type Theorems for Triangles in Convex Point Sets},
howpublished = {Courant Institute Geometry Seminar},
address = {New York, USA},
month = {April},
year = {2016},
}
@Misc{talk14,
title = {Encoding Arguments},
howpublished = {Probability, Combinatorics, and Geometry: Ninth Annual Workshop},
address = {Bellairs Research Institute, Holetown, Barbados},
month = {April},
year = {2014}
}
@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
}