 |
|
|
|||||||||||||||||||||
|
||||||||||||||||||||||
|
|||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||
|
|
||||||
 |
|
|
|
||||
| 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.
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. To appear. 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, Proc. 25th ACM Symposium on Computational Geometry (SoCG), Aarhus, 2009, p163-168. A short abstract appeared in the 25th European Workshop on Computational Geometry (EWCG), Brussel, 2009. With Freek van Walderveen: Four-dimensional Hilbert curves for R-trees, Proc. Workshop on Algorithm Engineering and Experiments (ALENEX), New York, 2009.
First published in 2008With Freek van Walderveen: Locality and bounding-box quality of two-dimensional space-filling curves, Computational Geometry (CGTA), to appear. An extended abstract appeared in the 16th European Symposium on Algorithms (ESA), Karlsruhe, 2008.[Full manuscript] With Freek van Walderveen: Space-filling curve properties for efficient spatial index structures, Proc. 24th European Workshop on Computational Geometry (EWCG), 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" (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, Proc. 24th European Workshop on Computational Geometry (EWCG), Nancy, 2008, p75-78.
First published in 2007With Marc Benkert, Moritz Kroll, and Martin Nöllenburg: Algorithms for multi-criteria one-sided boundary labeling, Proc. 15th International Symposium on Graph Drawing (GD), Sydney, 2007, LNCS 4875:243-254.[Find 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), to appear. A brief abstract of parts of the paper appeared in 22nd European Workshop on Computational Geometry, Eindhoven, 2005. A more elaborate abstract appeared in 10th Int. Workshop on Algorithms and Data Structures, Halifax, 2007. With Mark de Berg, Shripad Thite, and Laura Toma: I/O-efficient map overlay and point location in low-density subdivisions, Proc. 18th International Symposium on Algorithms and Computation (ISAAC), Sendai, 2007, LNCS 4835:500-511. A brief abstract appeared in 23rd European Workshop on Computational Geometry, Graz, 2007. 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, on-line first An extended abstract appeared in the 14th European Symposium on Algorithms (ESA)[PDF-file of conference version 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, Proc. 22nd European Workshop on Computational Geometry (EWCG), 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, Proc. 7th Latin American Theoretical Informatics conference (LATIN), Valdivia, 2006, LNCS 3887:580-591.
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 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.[PDF-file from electronic proceedings]
| |
|
||||||||||||||||
|
||||||||||||||||
