 |
|
|
|||||||||||||||||||||
|
||||||||||||||||||||||
|
|||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||
|
|
||||||
 |
|
|
|
||||
| Publications in this list are ordered by the year of first appearance of any version,
whether refereed or not.
A list ordered by medium (journal, refereed international conference, or other) can be found in my Curriculum Vitae. Submitted papers of which no preliminary version or abstract has appeared yet.With George Fletcher and Jelle Hellings: Efficient external-memory bisimulation on DAGs, 2011. Submitted.[Not available for downloading at this time; please mail me for a copy.] Single-authored: I/O-optimal algorithms on grid graphs, 2011. Extended abstract and appendices submitted to conference.
First published in 2011With Kevin Buchin, Tal Milea, and Okke Schrijvers: Shortest-Paths Preserving Metro Maps, poster with abstract in Proc. 19th International Symposium on Graph Drawing (GD), Eindhoven, 2011. To appear.[Not available for downloading at this time; please mail me for a copy.] Single-authored: An inventory of three-dimensional Hilbert space-filling curves, arXiv:1109.2323. With Anne Driemel, Maarten Löffler, and Rodrigo Silveira: Flow computations on imprecise terrains, Proc. 12th Algorithms and Data Structures Symposium (WADS), New York, 2011, LNCS 6844:350-361. A brief abstract appeared in 27th European Workshop on Computational Geometry (EuroCG), Morschach, 2011 With Constantinos Tsirogiannis: Flow on noisy terrains: an experimental evaluation, Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), Chicago, 2011. To appear. A brief abstract appeared in 27th European Workshop on Computational Geometry (EuroCG), Morschach, 2011 With Mark de Berg and Constantinos Tsirogiannis: Implicit flow routing on terrains with applications to surface networks and drainage structures, Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, 2011, p285-296. A brief abstract of parts of this work appeared as "Implicit flow routing on triangulated terrains" in 27th European Workshop on Computational Geometry, Morschach, 2011
First published in 2010Single-authored: Recursive tilings and space-filling curves with little fragmentation, Abstracts 26th European Workshop on Computational Geometry (EuroCG), Dortmund, 2010, p185-188.[Full manuscript from Arxiv, slides, fast-forward slides]
First published in 2009With Jeremy Fishman and Laura Toma: Improved visibility computation on massive grid terrains, Proc. 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), Seattle, 2009, p121-130. Best-paper award.[PDF-file] With Jeffrey Janssen: Simple I/O-efficient flow accumulation on grid terrains, Abstract collection Workshop on Massive Data Algorithms, Aarhus, 2009. With Mark de Berg and Constantinos Tsirogiannis: Visibility maps of realistic terrains have linear smoothed complexity, Journal of Computational Geometry (JoCG), 1(1), 2010, p57-71. A brief abstract appeared in 25th European Workshop on Computational Geometry, Brussel, 2009.
An extended abstract appeared in the 25th ACM Symposium on Computational Geometry, Aarhus, 2009. With Freek van Walderveen: Four-dimensional Hilbert curves for R-trees, Proc. 11th Workshop on Algorithm Engineering and Experiments (ALENEX), New York, 2009, p63-73. Full version to appear in Journal of Experimental Algorithms
First published in 2008With Freek van Walderveen: Locality and bounding-box quality of two-dimensional space-filling curves, Computational Geometry (CGTA), 43(2), 2010, p131-147. An extended abstract appeared in the 16th European Symposium on Algorithms (ESA), Karlsruhe, 2008.[Full manuscript from Arxiv] With Freek van Walderveen: Space-filling curve properties for efficient spatial index structures, Abstracts 24th European Workshop on Computational Geometry (EuroCG), Nancy, 2008, p51-54. More information about the results in this brief abstract can be found in our papers
"Locality and bounding-box quality of two-dimensional space-filling curves" and "Four-dimensional Hilbert curves for R-trees literal["] (see above). With Maarten Löffler, Elena Mumford, Matthew O'Meara, Jack Snoeyink, and Bettina Speckmann: Colour patterns for polychromatic four-colourings of rectangular subdivisions, Abstracts 24th European Workshop on Computational Geometry (EuroCG), Nancy, 2008, p75-78.
First published in 2007With Marc Benkert, Moritz Kroll, and Martin Nöllenburg: Algorithms for multi-criteria one-sided boundary labeling, Journal of Graph Algorithms and Applications (JGAA), 13(3), 2009, p289-317. An extended abstract appeared in 15th Int. Symposium on Graph Drawing (GD), Sydney, 2007.[PDF-file from publisher] With Mark de Berg, Otfried Cheong, Jung-Gun Lim, and Laura Toma: The complexity of flow on fat terrains and its I/O-efficient computation, Computational Geometry (CGTA), 43(4), 2010, p331-356. A brief abstract of parts of the paper appeared as "River networks and watershed maps of triangulated terrains revisited", in 22nd European Workshop on Computational Geometry, Eindhoven, 2005.
A more elaborate abstract appeared as "I/O-efficient flow modeling on fat terrains", in 10th Int. Workshop on Algorithms and Data Structures, Halifax, 2007. With Mark de Berg, Shripad Thite, and Laura Toma: Star-Quadtrees and Guard-Quadtrees: I/O-Efficient Indexes for Fat Triangulations and Low-Density Planar Subdivisions, Computational Geometry (CGTA), 43(5), 2010, p493-513. A brief abstract appeared in 23rd European Workshop on Computational Geometry, Graz, 2007, and an extended abstract appeared in the 18th International Symposium on Algorithms and Computation (ISAAC), Sendai, 2007, both under the title "I/O-efficient map overlay and point location in low-density subdivisions". With Otfried Cheong and Mira Lee: Computing a minimum-dilation spanning tree is NP-hard, Computational Geometry (CGTA), 41(3), 2008, p188-205. An extended abstract appeared in Computing: the Australasian Theory Symposium, Ballarat, 2007. With Laura Toma and Yi Zhuang: Computing visibility on terrains in external memory, Journal of Experimental Algorithmics (JEA), 13:5, 2009. An extended abstract appeared in Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, 2007.
First published in 2006With Sergio Cabello, Marc van Kreveld, and Bettina Speckmann: Algorithmic aspects of proportional symbol maps, Algorithmica, 58(3), 2010, p543-565. An extended abstract appeared in the 14th European Symposium on Algorithms (ESA)[Find PDF-file from publisher] With Hee-Kap Ahn, Mark de Berg, Otfried Cheong, Frank van der Stappen, and Laura Toma: River networks and watershed maps of triangulated terrains revisited, Abstracts 22nd European Workshop on Computational Geometry (EuroCG), Delphi, 2006, p173-176. The results presented in this abstract can be found in the paper "The complexity of flow on fat terrains and its I/O-efficient computation" mentioned above. With Laura Toma: I/O-efficient algorithms on near-planar graphs, Journal on Graph Algorithms and Applications (JGAA), 15(4), 2011, p503-532. An extended abstract appeared in 7th Latin American Theoretical Informatics conference.
First published in 2005With Mirela Tanase and Remco Veltkamp: Multiple polyline to polygon matching, Proc. 16th International Symposium on Algorithms and Computation (ISAAC), Sanya, 2005, LNCS 3827:60-70.[PDF-file of technical report, slides] With Boris Aronov, Mark de Berg, Otfried Cheong, Joachim Gudmundsson and Antoine Vigneron: Sparse geometric graphs with small dilation, Computational Geometry (CGTA), 40(3), 2008, p207-219. An extended abstract appeared in 16th International Symposium on Algorithms and Computation, Sanya, 2005. With Mark de Berg and Micha Streppel: Efficient c-oriented range searching with DOP-trees, Computational Geometry (CGTA), 42(3), 2009, p250-267. An extended abstract appeared in 13th European Symposium on Algorithms, Mallorca, 2005. With Lars Arge, Andrew Danner and Norbert Zeh: I/O-efficient hierarchical watershed decomposition of grid terrain models, Proc. 12th International Symposium on Spatial Data Handling (SDH), Vienna, 2006, p825-844. An extended abstract, with a focus on more technical details, appeared as "Computing Pfafstetter labellings I/O-efficiently" in the 1st Workshop on Massive Geometric Data Sets, Pisa, 2005 With Lars Arge and Mark de Berg: Cache-oblivious R-trees, Algorithmica, 53(1), 2009, p50-68. An extended abstract appeared in 21st ACM Symposium on Computational Geometry, Pisa, 2005.
With Marc Benkert, Joachim Gudmundsson, and Alexander Wolff: Constructing minimum-interference networks, Computational Geometry (CGTA), 40(3), 2008, p179-272. A brief abstract appeared in 21st European Workshop on Computational Geometry, Eindhoven, 2005. A more elaborate abstract appeared in SOFSEM 2006.
First published in 2004With Lars Arge, Mark de Berg, and Ke Yi: The Priority R-Tree: a practically efficient and worst-case-optimal R-tree, ACM Transactions on Algorithms, 4(1):9, 2008. An extended abstract appeared in 23rd Symp. of the ACM Special Interest Group on Management of Data (SIGMOD), Paris, 2004. Also available as a technical report and included in my PhD thesis. The journal version contains minor revisions.[PDF-file of technical report] Results on geometric networks and data structures, PhD thesis, Utrecht University, 2004. Adviser: Mark de Berg. The thesis is a collection of articles some of which are related to each other. With Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Naoki Katoh, and Alexander Wolff: Optimal spanners for axis-aligned rectangles, Computational Geometry (CGTA), 30(1), 2005, p59-77. A brief abstract appeared in 20th European Workshop on Computational Geometry, Sevilla, 2004.
Full text also included in my PhD thesis. The journal version contains minor revisions.
First published in 2003With Jae-Sook Cheong and Frank van der Stappen: Computing all immobilizing grasps of a simple polygon with few contacts, Algorithmica, 44(2), 2006, p117-136. Preliminary versions appeared in 14th Int. Symp. on Algorithms and Computation (ISAAC), Kyoto, 2003, and as a technical report.[PDF-file of technical report] With Joachim Gudmundsson and Marc van Kreveld: Constrained higher-order Delaunay triangulations, Computational Geometry (CGTA), 30(3), 2005, p271-277. A brief abstract appeared in 19th European Workshop on Computational Geometry, Bonn, 2003 With Mark de Berg: Significant-presence range queries in categorical data, Proc. 8th Int. Workshop on Algorithms and Data Structures (WADS), Ottawa, 2003, LNCS 2748:462-473. First abstract appeared in 19th European Workshop on Computational Geometry, Bonn, 2003.
Full text available as a technical report (also included in my PhD thesis)
First published in 2002With Joachim Gudmundsson, Sang-Min Park, Chan-Su Shin, and Alexander Wolff: Facility location and the geometric minimum-diameter spanning tree, Computational Geometry (CGTA), 27(1), 2004, p87-106. First abstract appeared in 18th European Workshop on Computational Geometry, Warszawa, 2002; a more elaborate abstract appeared in 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), Roma, 2002. Full text also included in my PhD thesis.[PDF-file of Chapter 6 in my PhD thesis, PDF-file of PhD thesis bibliography] With Mark de Berg and Joachim Gudmundsson: Box-trees for collision checking in industrial installations, Computational Geometry (CGTA), 28(2-3), 2004, p113-135. First abstract appeared in 18th ACM Symposium on Computational Geometry, Barcelona, 2002. Extended version available as a technical report
First published in 2001With Pankaj Agarwal, Mark de Berg, Joachim Gudmundsson, and Mikael Hammar: Box-trees and R-trees with near-optimal query time, Discrete & Computational Geometry, 28(3), 2002, p291-312. First abstract appeared in 17th ACM Symposium on Computational Geometry, Medford, 2001. Also available: technical report. Later included in my PhD thesis, with slightly better bounds than in the report, conference, and journal versions.[PDF-file of Chapter 3 in my PhD thesis, PDF-file of PhD thesis bibliography, slides]
First published in 1999With Hans Bodlaender: Finding a minimal tree in a polygon with its medial axis, Proc. 11th Canadian Conference on Computational Geometry (CCCG), Vancouver, 1999. Also part of my Master's thesis. | |
|
||||||||||||||||
|
||||||||||||||||
