Publications

Conference Proceedings

Robust Classification of Dynamic Bichromatic Point Sets in \(\R^2\)

Erwin Glazenburg, Marc Kreveld, Frank Staals

Proc. 35th International Symposium on Algorithms and Computation, 2024

To appear
Download Local Copy View Slides Export Citation 
@inproceedings{dynamicsvm2024,
  author = {Glazenburg, Erwin and Kreveld, Marc and Staals, Frank},
  title = {Robust Classification of Dynamic Bichromatic Point Sets in $\R^2$},
  booktitle = {Proc. 35th International Symposium on Algorithms and Computation},
  year = {2024},
  location = {Sydney, Australia},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {classification},
  note = {To appear},
}

Robust Bichromatic Classification using Two Lines

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, Frank Staals

Proc. 35th International Symposium on Algorithms and Computation, 2024

To appear
Download Local Copy View Slides Export Citation 
@inproceedings{twolineseparator2024,
  author = {Glazenburg, Erwin and van der Horst, Thijs and Peters, Tom and Speckmann, Bettina and Staals, Frank},
  title = {Robust Bichromatic Classification using Two Lines},
  booktitle = {Proc. 35th International Symposium on Algorithms and Computation},
  year = {2024},
  location = {Sydney, Australia},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {classification},
  note = {To appear},
}

The Complexity of Geodesic Spanners using Steiner Points

Sarita de Berg, Tim Ophelders, Irene Parada, Frank Staals, Jules Wulms

Proc. 35th International Symposium on Algorithms and Computation, 2024

To appear
Download Local Copy View Slides Export Citation 
@inproceedings{steinerspanners2024,
  author = {de Berg, Sarita and Ophelders, Tim and Parada, Irene and Staals, Frank and Wulms, Jules},
  title = {The Complexity of Geodesic Spanners using Steiner Points},
  booktitle = {Proc. 35th International Symposium on Algorithms and Computation},
  year = {2024},
  location = {Sydney, Australia},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {geodesic},
  note = {To appear},
}

Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

Ivor van der Hoog, André Nusser, Eva Rotenberg, Frank Staals

Proc. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), 2024

Download Local Copy View Slides Export Citation 
@inproceedings{squareconnectivity2024,
  author = {van der Hoog, Ivor and Nusser, Andr{\'{e}} and Rotenberg, Eva and Staals, Frank},
  title = {Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs},
  booktitle = {Proc. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  year = {2024},
  location = {Bratislava, Slovakia},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  pages = {63:1--63:17},
  isbn = {978-3-95977-335-5},
  issn = {1868-8969},
  volume = {306},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {datastructures},
  url = {https://doi.org/10.4230/LIPIcs.MFCS.2024.63},
  doi = {10.4230/LIPIcs.MFCS.2024.63},
  keywords = {Computational geometry, planar geometry, data structures, geometric intersection graphs, fully-dynamic algorithms},
}

Exact solutions to the Weighted Region Problem

Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira, Frank Staals

Proc. 36th Canadian Conference on Computational Geometry (CCCG), 2024

Download Local Copy View Slides Export Citation 
@inproceedings{wrp2024,
  author = {de Berg, Sarita and Esteban, Guillermo and I. Silveira, Rodrigo and Staals, Frank},
  title = {Exact solutions to the Weighted Region Problem},
  booktitle = {Proc. 36th Canadian Conference on Computational Geometry (CCCG)},
  year = {2024},
  location = {St. Catharines, Canada},
  numpages = {8},
  category = {wrp},
}

Fine-Grained Complexity of Earth Mover’s Distance under Translation

Karl Bringmann, Frank Staals, Karol Węgrzycki, Geert van Wordragen

Proc. 40th Annual Symposium on Computational Geometry, 2024

Download Local Copy View Slides Export Citation 
@inproceedings{emdut2024,
  author = {Bringmann, Karl and Staals, Frank and W\k{e}grzycki, Karol and van Wordragen, Geert},
  title = {Fine-Grained Complexity of Earth Mover's Distance under Translation},
  booktitle = {Proc. 40th Annual Symposium on Computational Geometry},
  year = {2024},
  location = {Athens, Greece},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {other},
  doi = {4230/LIPIcs.SoCG.2024.25},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2024.25},
  volume = {293},
  pages = {25:1--25:17},
}

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain

Sarita de Berg, Till Miltzow, Frank Staals

Proc. 40th Annual Symposium on Computational Geometry, 2024

Download Local Copy View Slides Export Citation 
@inproceedings{twoptsp2024,
  author = {de Berg, Sarita and Miltzow, Till and Staals, Frank},
  title = {Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain},
  booktitle = {Proc. 40th Annual Symposium on Computational Geometry},
  year = {2024},
  location = {Athens, Greece},
  keywords = {data structure, polygonal domain, geodesic distance, shortest path},
  category = {geodesic},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {4230/LIPIcs.SoCG.2024.17},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2024.17},
  volume = {293},
  pages = {17:1--17:16},
}

The Complexity of Geodesic Spanners

Sarita de Berg, Marc van Kreveld, Frank Staals

Proc. 39th Annual Symposium on Computational Geometry, 2023

Download Local Copy View Slides Export Citation 
@inproceedings{geodesic_spanners2023,
  author = {de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
  title = {The Complexity of Geodesic Spanners},
  booktitle = {Proc. 39th Annual Symposium on Computational Geometry},
  year = {2023},
  location = {Dallas, United States},
  keywords = {spanner, simple polygon, geodesic distance, complexity},
  category = {geodesic},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2023.16},
  pages = {16:1--16:16},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2023.16},
  volume = {258},
}

Shortest Paths in Portalgons

Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, Frank Staals

Proc. 39th Annual Symposium on Computational Geometry, 2023

Download Local Copy View Slides Export Citation 
@inproceedings{portalgons2023,
  author = {L{\"o}ffler, Maarten and Ophelders, Tim and
                 I. Silveira, Rodrigo and Staals, Frank},
  title = {Shortest Paths in Portalgons},
  booktitle = {Proc. 39th Annual Symposium on Computational Geometry},
  year = {2023},
  location = {Dallas, United States},
  keywords = {polyhedral surfaces, shortest paths, geodesic distance, Delaunay triangulation},
  category = {geodesic},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2023.48},
  pages = {48:1--48:16},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2023.48},
  volume = {258},
}

Segment Visibility Counting Queries in Polygons

Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, Frank Staals

Proc. 33th International Symposium on Algorithms and Computation, 2022

Download Local Copy View Slides Export Citation 
@inproceedings{segmentvis2022,
  author = {Buchin, Kevin and Custers, Bram and van der Hoog, Ivor and
                 L{\"o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel
                 and  Staals, Frank},
  title = {Segment Visibility Counting Queries in Polygons},
  booktitle = {Proc. 33th International Symposium on Algorithms and Computation},
  year = {2022},
  keywords = {Visibility, Data Structure, Polygons, Complexity},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  pages = {58:1--58:16},
  volume = {248},
  editor = {Bae, Sang Won and Park, Heejin},
  doi = {10.4230/LIPIcs.ISAAC.2022.58},
  url = {https://doi.org/10.4230/LIPIcs.ISAAC.2022.58},
}

Efficient Fréchet distance queries for segments

Buchin Maike, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, Frank Staals

Proc. 30th European Symposium on Algorithms, 2022

Download Local Copy View Slides Export Citation 
@inproceedings{frechet_segmentqueries2022,
  author = {Maike, Buchin and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and
                 I. Silveira, Rodrigo and Staals, Frank},
  title = {Efficient Fréchet distance queries for segments},
  booktitle = {Proc. 30th European Symposium on Algorithms},
  year = {2022},
  location = {Potsdam, Germany},
  numpages = {14},
  pages = {29:1--29:14},
  keywords = {Computational Geometry, Data Structures, Fréchet distance},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  volume = {244},
  editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  doi = {10.4230/LIPIcs.ESA.2022.29},
  url = {https://doi.org/10.4230/LIPIcs.ESA.2022.29},
}

Chromatic \(k\)-Nearest Neighbor Queries

Thijs van der Horst, Maarten Löffler, Frank Staals

Proc. 30th European Symposium on Algorithms, 2022

Download Local Copy View Slides Export Citation 
@inproceedings{chromatic_knn2022,
  author = {van der Horst, Thijs and L{\"o}ffler, Maarten and Staals, Frank},
  title = {Chromatic $k$-Nearest Neighbor Queries},
  booktitle = {Proc. 30th European Symposium on Algorithms},
  year = {2022},
  location = {Potsdam, Germany},
  numpages = {15},
  pages = {67:1--67:15},
  keywords = {data structure, nearest neighbor, classification},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  volume = {244},
  editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  doi = {10.4230/LIPIcs.ESA.2022.67},
  url = {https://doi.org/10.4230/LIPIcs.ESA.2022.67},
}

Dynamic Data Structures for \(k\)-Nearest Neighbor Queries

Sarita de Berg, Frank Staals

Proc. 32th International Symposium on Algorithms and Computation, 2021

Invited for a Special Issue on ISAAC 2021 in CGTA
Download Local Copy View Slides Export Citation 
@incollection{dynamic_knn2021,
  author = {de Berg, Sarita and Staals, Frank},
  title = {Dynamic Data Structures for $k$-Nearest Neighbor Queries},
  booktitle = {Proc. 32th International Symposium on Algorithms and Computation},
  year = {2021},
  volume = {212},
  pages = {14:1--14:14},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Fukuoka, Japan},
  category = {datastructures},
  doi = {10.4230/LIPIcs.ISAAC.2021.14},
  url = {https://doi.org/10.4230/LIPIcs.ISAAC.2021.14},
  note = {Invited for a Special Issue on ISAAC 2021 in CGTA},
}

Terrain prickliness: theoretical grounds for low complexity viewsheds

Ankush Acharyya, Ramesh Jallu, Maarten Löffler, Gert Meijer, Maria Saumell, Rodrigo I. Silveira, Frank Staals, Hans Raj Tiwary

Proc. 11th International Conference on Geographic Information Science, 2021

Download Local Copy View Slides Export Citation 
@incollection{prickliness2021,
  author = {Acharyya, Ankush and Jallu, Ramesh and  L{\"o}ffler, Maarten and
                 Meijer, Gert and Saumell, Maria and I. Silveira, Rodrigo and
                 Staals, Frank and Raj Tiwary, Hans},
  title = {Terrain prickliness: theoretical grounds for low complexity viewsheds},
  booktitle = {Proc. 11th International Conference on Geographic Information Science},
  year = {2021},
  location = {(online)},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  numpages = {14},
  pages = {10:1--10:16},
  category = {terrains},
  doi = {10.4230/LIPIcs.GIScience.2021.II.10},
  url = {https://doi.org/10.4230/LIPIcs.GIScience.2021.II.10},
}

Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Ivor van der Hoog, Mees van der Kerkhof, Marc van Kreveld, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen

Proc. 2021 WADS Algorithms and Data Structures Symposium, 2021

Download Local Copy View Slides Export Citation 
@incollection{pixelpolygons2021,
  author = {van der Hoog, Ivor and van der Kerkhof, Mees and van Kreveld, Marc and
                 L{\"o}ffler, Maarten and Staals, Frank and Urhausen, J{\'e}r{\^o}me
                 and Vermeulen, Jordi L.},
  title = {Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance},
  booktitle = {Proc. 2021 WADS Algorithms and Data Structures Symposium},
  series = {LNCS},
  year = {2021},
  location = {Halifax, Canada (online)},
  publisher = {Springer},
  category = {other},
  pages = {627--640},
  doi = {10.1007/978-3-030-83508-8_45},
  url = {https://doi.org/10.1007/978-3-030-83508-8_45},
}

Covering a set of line segments with a few squares

Joachim Gudmundsson, Mees van de Kerkhof, André van Renssen, Frank Staals, Lionov Wiratma, Sampson Wong

Proc. 12th International Conference on Algorithms and Complexity, 2021

Invited for a special issue on CIAC 2021 in Theoretical Computer Science (TCS)
Download Local Copy View Slides Export Citation 
@incollection{multihotspots2021,
  author = {Gudmundsson, Joachim  and van de Kerkhof, Mees and van Renssen, Andr{\'e}
                 and Staals, Frank and Wiratma, Lionov and Wong, Sampson},
  title = {Covering a set of line segments with a few squares},
  booktitle = {Proc. 12th International Conference on Algorithms and Complexity},
  year = {2021},
  series = {LNCS},
  editor = {Calamoneri, Tiziana and Cor{\`o}, Federico},
  location = {Larnaca, Cyprus (online)},
  publisher = {Springer},
  pages = {286--299},
  category = {trajectories},
  doi = {10.1007/978-3-030-75242-2_20},
  url = {https://doi.org/10.1007/978-3-030-75242-2_20},
  note = {Invited for a special issue on CIAC 2021 in Theoretical Computer Science (TCS)},
}

Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Matias Korman, André van Renssen, Marcel Roeloffzen, Frank Staals

Proc. 47th International Colloquium on Automata, Languages and Programming, 2020

Download Local Copy View Slides Export Citation 
@incollection{kinetic_gvd2020,
  author = {Korman, Matias and van Renssen, Andr{\'e} and Roeloffzen, Marcel and Staals, Frank},
  title = {Kinetic Geodesic Voronoi Diagrams in a Simple Polygon},
  booktitle = {Proc. 47th International Colloquium on Automata, Languages and Programming},
  year = {2020},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Saarbrücken, Germany (online)},
  category = {geodesic},
  pages = {75:1--75:17},
  volume = {168},
  doi = {10.4230/LIPIcs.ICALP.2020.75},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2020.75},
}

Trajectory Visibility

Patrick Eades, Ivor van der Hoog, Maarten Löffler, Frank Staals

Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Download Local Copy View Slides Export Citation 
@incollection{trajectoryvisibility2020,
  author = {Eades, Patrick and van der Hoog, Ivor and L{\"o}ffler, Maarten
                 and Staals, Frank},
  title = {Trajectory Visibility},
  booktitle = {Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory},
  year = {2020},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Torshaven, Faroe Islands (online)},
  category = {datastructures},
  url = {https://doi.org/10.4230/LIPIcs.SWAT.2020.23},
  doi = {10.4230/LIPIcs.SWAT.2020.23},
  pages = {23:1--23:22},
  volume = {162},
}

Maximum Physically Consistent Trajectories

Bram Custers, Mees van de Kerkhof, Wouter Meulemans, Bettina Speckmann, Frank Staals

Proc. 27th International Conference on Advances in Geographic Information Systems, 2019

Won Best Paper at SIGSPATIAL ’19
Download Local Copy View Slides Export Citation 
@inproceedings{trajectoryoutliers2019,
  author = {Custers, Bram and van de Kerkhof, Mees and Meulemans, Wouter and
                 Speckmann, Bettina and Staals, Frank},
  title = {Maximum Physically Consistent Trajectories},
  booktitle = {Proc. 27th International Conference on Advances in Geographic
                   Information Systems},
  series = {SIGSPATIAL '19},
  year = {2019},
  location = {Chicago, Illinois},
  numpages = {10},
  pages = {79--88},
  publisher = {ACM},
  category = {trajectories},
  doi = {10.1145/3347146.3359363},
  url = {https://dl.acm.org/authorize?N690079},
  note = {Won Best Paper at SIGSPATIAL '19},
}

An Experimental Evaluation of Grouping Definitions for Moving Entities

Lionov Wiratma, Marc van Kreveld, Maarten Löffler, Frank Staals

Proc. 27th International Conference on Advances in Geographic Information Systems, 2019

Download Local Copy View Slides Export Citation 
@inproceedings{groupingexperiments2019,
  author = {Wiratma, Lionov and van Kreveld, Marc and L{\"o}ffler, Maarten
                and Staals, Frank},
  title = {An Experimental Evaluation of Grouping Definitions for Moving Entities},
  booktitle = {Proc. 27th International Conference on Advances in Geographic
                   Information Systems},
  series = {SIGSPATIAL '19},
  year = {2019},
  location = {Chicago, Illinois},
  numpages = {10},
  publisher = {ACM},
  pages = {89--98},
  doi = {10.1145/3347146.3359346},
  url = {https://dl.acm.org/authorize?N690070},
  category = {trajectories},
}

Most vital segment barriers

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals

Proc. 2019 WADS Algorithms and Data Structures Symposium, 2019

Download Local Copy View Slides Export Citation 
@incollection{blocking_stick2019,
  author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Polishchuk, Valentin and
                 Staals, Frank},
  title = {Most vital segment barriers},
  booktitle = {Proc. 2019 WADS Algorithms and Data Structures Symposium},
  series = {LNCS},
  year = {2019},
  location = {Edmonton, Alberta, Canada},
  numpages = {14},
  publisher = {Springer},
  category = {geodesic},
  doi = {10.1007/978-3-030-24766-9_36},
  url = {https://doi.org/10.1007/978-3-030-24766-9_36},
  pages = {495--509},
  editor = {Friggstad, Zachary and Sack, J{\"o}rg-R{\"u}diger
                 and Salavatipour, Mohammad R},
}

Convex Partial Transversals of Planar Regions

Vahideh Keikha, Mees van der Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, Lionov Wiratma

Proc. 29th International Symposium on Algorithms and Computation, 2018

Download Local Copy View Slides Export Citation 
@incollection{convex_kgon2018,
  author = {Keikha, Vahideh and van der Kerkhof, Mees and van Kreveld, Marc and
                 Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                 and Urhausen, J{\'e}r{\^o}me and Vermeulen, Jordi L.
                 and Wiratma, Lionov},
  title = {Convex Partial Transversals of Planar Regions},
  booktitle = {Proc. 29th International Symposium on Algorithms and Computation},
  year = {2018},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Yilan, Taiwan},
  numpages = {12},
  category = {other},
  volume = {123},
  url = {http://drops.dagstuhl.de/opus/volltexte/2018/10000},
  doi = {10.4230/LIPIcs.ISAAC.2018.52},
}

An experimental comparison of two definitions for groups of moving entities

Lionov Wiratma, Maarten Löffler, Frank Staals

Proc. 10th International Conference on Geographic Information Science, 2018

Download Local Copy View Slides Export Citation 
@incollection{grouping_exp2018,
  author = {Wiratma, Lionov and L{\"o}ffler, Maarten and Staals, Frank},
  title = {An experimental comparison of two definitions for groups of moving  entities},
  booktitle = {Proc. 10th International Conference on Geographic Information Science},
  year = {2018},
  location = {Melborne, Australia},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  volume = {114},
  numpages = {6},
  pages = {64:1--64:6},
  category = {trajectories},
  doi = {10.4230/LIPIcs.GISCIENCE.2018.64},
  url = {https://doi.org/10.4230/LIPIcs.GISCIENCE.2018.64},
  project = {groupingexperiments2019},
}

Convexity-Increasing Morphs of Planar Graphs

Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals, Darren Strash

Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science, 2018

Download Local Copy View Slides Export Citation 
@inproceedings{convexmorphing2018,
  author = {Kleist, Linda and Klemz, Boris and Lubiw, Anna and Schlipf, Lena
                 and Staals, Frank and Strash, Darren},
  title = {Convexity-Increasing Morphs of Planar Graphs},
  booktitle = {Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science},
  series = {LNCS},
  volume = {11159},
  year = {2018},
  location = {Cottbus, Germany},
  publisher = {Springer},
  numpages = {12},
  pages = {318--330},
  category = {graphs},
  keywords = {planar graphs, graph drawing},
  doi = {10.1007/978-3-030-00256-5_26},
  url = {https://doi.org/10.1007/978-3-030-00256-5_26},
}

Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polgyon

Pankaj K. Agarwal, Lars Arge, Frank Staals

Proc. 34th Annual Symposium on Computational Geometry, 2018

Download Local Copy View Slides Export Citation 
@inproceedings{dyn_geod_nn2018,
  author = {Agarwal, Pankaj K. and Arge, Lars and Staals, Frank},
  title = {Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polgyon},
  booktitle = {Proc. 34th Annual Symposium on Computational Geometry},
  year = {2018},
  editor = {Bettina Speckmann and Csaba D. T{\'o}th},
  location = {Budapest, Hungary},
  numpages = {14},
  keywords = {data structure, simple polygon, geodesic distance
                , nearest neighbor searching, shallow cutting},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  pages = {4:1--4:14},
  isbn = {978-3-95977-066-8},
  issn = {1868-8969},
  volume = {99},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2018.4},
  doi = {10.4230/LIPIcs.SoCG.2018.4},
}

Agglomerative Clustering of Growing Squares

Thom Castermans, Bettina Speckmann, Frank Staals, Kevin Verbeek

Proc. 2018 Latin American Theoretical Informatics Symposium, 2018

Download Local Copy View Slides Export Citation 
@incollection{zoomingsquares2018,
  author = {Castermans, Thom and Speckmann, Bettina and Staals, Frank
                 and Verbeek, Kevin},
  title = {Agglomerative Clustering of Growing Squares},
  booktitle = {Proc. 2018 Latin American Theoretical Informatics Symposium},
  editor = {Bender, Michael A. and Farach-Colton, Mart{\'i}n and Mosteiro, Miguel A.},
  series = {LNCS},
  year = {2018},
  location = {Buenos Aires, Argentina},
  numpages = {14},
  publisher = {Springer},
  category = {datastructures},
  keywords = {kinetic data structures},
  pages = {260--274},
  isbn = {978-3-319-77404-6},
  url = {https://doi.org/10.1007/978-3-319-77404-6_20},
  doi = {10.1007/978-3-319-77404-6_20},
}

Clustering Trajectories for Map Construction

Kevin Buchin, Maike Buchin, David Duran, Brittany Terese Fasy, Roel Jacobs, Vera Sacristan, Rodrigo I. Silveira, Frank Staals, Carola Wenk

Proc. 25th International Conference on Advances in Geographic Information Systems, 2017

Download Local Copy View Slides Export Citation 
@inproceedings{bundles2017,
  author = {Buchin, Kevin and Buchin, Maike and Duran, David and
                  Terese Fasy, Brittany and Jacobs, Roel and
                  Sacristan, Vera and I. Silveira, Rodrigo and Staals, Frank and
                  Wenk, Carola},
  title = {Clustering Trajectories for Map Construction},
  booktitle = {Proc. 25th International Conference on Advances in Geographic
                   Information Systems},
  series = {SIGSPATIAL '17},
  year = {2017},
  location = {Redondo Beach, California},
  numpages = {10},
  publisher = {ACM},
  url = {https://dl.acm.org/authorize?N42692},
  doi = {10.1145/3139958.3139964},
  keywords = {trajectory, moving entity, hotspot, geometric algorithms},
  category = {trajectories},
}

Computing the Expected Value and the Variance of Geometric Measures

Frank Staals, Constantinos Tsirogiannis

Proc. 19th Workshop on Algorithm Engineering & Experiments (ALENEX), 2017

Invited for a special issue on ALENEX 2017 in the ACM Journal of Experimental Algorithmics
Download Local Copy View Slides Export Citation 
@inproceedings{expected_measures2017,
  author = {Staals, Frank and Tsirogiannis, Constantinos},
  title = {Computing the Expected Value and the Variance of Geometric Measures},
  booktitle = {Proc. 19th Workshop on Algorithm Engineering \& Experiments (ALENEX)},
  year = {2017},
  location = {Barcelona, Spain},
  numpages = {15},
  keywords = {stochastic point-sets, geometric measures, convex hull volume},
  category = {other},
  publisher = {SIAM},
  pages = {232--246},
  doi = {10.1137/1.9781611974768.19},
  url = {https://dl.acm.org/authorize?N690071},
  note = {Invited for a special issue on ALENEX 2017 in the ACM Journal of Experimental Algorithmics},
}

A Refined Definition for Groups of Moving Entities and its Computation

Marc van Kreveld, Maarten Löffler, Frank Staals, Lionov Wiratma

Proc. 27th International Symposium on Algorithms and Computation, 2016

Invited for a special issue on ISAAC 2016 in the International Journal on Computational Geometry and its Applications
Download Local Copy View Slides Export Citation 
@inproceedings{refined_grouping2016,
  author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank and
                 Wiratma, Lionov},
  title = {A Refined Definition for Groups of Moving Entities and its Computation},
  booktitle = {Proc. 27th International Symposium on
                 Algorithms and Computation},
  year = {2016},
  location = {Sydney, Australia},
  numpages = {12},
  isbn = {978-3-95977-026-2},
  issn = {1868-8969},
  keywords = {trajectories, grouping, moving entities},
  category = {trajectories},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {64},
  editor = {Seok-Hee Hong},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  url = {https://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.48},
  doi = {10.4230/LIPIcs.ISAAC.2016.48},
  note = {Invited for a special issue on ISAAC 2016 in the International Journal on Computational Geometry and its Applications},
}

Homotopy Measures for Representative Trajectories

Erin Chambers, Irina Kostitsyna, Maarten Löffler, Frank Staals

Proc. 24th European Symposium on Algorithms, 2016

Download Local Copy View Slides Export Citation 
@inproceedings{homotopymeasures2016,
  author = {Chambers, Erin and Kostitsyna, Irina and L{\"o}ffler, Maarten
                 and Staals, Frank},
  title = {Homotopy Measures for Representative Trajectories},
  booktitle = {Proc. 24th European Symposium on Algorithms},
  year = {2016},
  location = {Aarhus, Denmark},
  numpages = {17},
  pages = {27:1--27:17},
  keywords = {trajectories, representative, median, homotopy area},
  category = {trajectories},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  volume = {57},
  editor = {Piotr Sankowski and Christos Zaroliagis},
  doi = {10.4230/LIPIcs.ESA.2016.27},
  url = {https://dx.doi.org/10.4230/LIPIcs.ESA.2016.27},
}

Grouping Time-varying Data for Interactive Exploration

Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, Frank Staals

Proc. 32th Annual Symposium on Computational Geometry, 2016

Download Local Copy View Slides Export Citation 
@inproceedings{cake2016,
  author = {van Goethem, Arthur and van Kreveld, Marc and L{\"o}ffler, Maarten
                 and Speckmann, Bettina and Staals, Frank},
  title = {Grouping Time-varying Data for Interactive Exploration},
  booktitle = {Proc. 32th Annual Symposium on Computational Geometry},
  year = {2016},
  pages = {61:1--61:16},
  isbn = {978-3-95977-009-5},
  issn = {1868-8969},
  volume = {51},
  url = {https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.61},
  doi = {10.4230/LIPIcs.SoCG.2016.61},
  editor = {S{\'a}ndor Fekete and Anna Lubiw},
  location = {Boston, USA},
  numpages = {16},
  keywords = {trajectories, grouping, moving entity, data structures},
  category = {trajectories},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
}

On the complexity of minimum-link path problems

Irina Kostitsyna, Maarten Löffler, Frank Staals, Valentin Polishchuk

Proc. 32th Annual Symposium on Computational Geometry, 2016

Invited for a special issue on SoCG 2016 in the Journal of Computational Geometry
Download Local Copy View Slides Export Citation 
@inproceedings{minlinkpath2016,
  author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                 and Polishchuk, Valentin},
  title = {On the complexity of minimum-link path problems},
  booktitle = {Proc. 32th Annual Symposium on Computational Geometry},
  year = {2016},
  pages = {49:1--49:16},
  isbn = {978-3-95977-009-5},
  issn = {1868-8969},
  volume = {51},
  editor = {S{\'a}ndor Fekete and Anna Lubiw},
  url = {https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.49},
  doi = {10.4230/LIPIcs.SoCG.2016.49},
  location = {Boston, USA},
  numpages = {15},
  keywords = {minimum-link path, diffuse reflection, terrain, bit complexity, NP-hardness reduction},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {terrains},
  note = {Invited for a special issue on SoCG 2016 in the Journal of Computational Geometry},
}

Trajectory Grouping Structure under Geodesic Distance

Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, Frank Staals

Proc. 31th Annual Symposium on Computational Geometry, 2015

Download Local Copy View Slides Export Citation 
@inproceedings{geogrouping2015,
  author = {Kostitsyna, Irina and van Kreveld, Marc and L{\"o}ffler, Maarten and
                 Speckmann, Bettina and Staals, Frank},
  title = {Trajectory Grouping Structure under Geodesic Distance},
  booktitle = {Proc. 31th Annual Symposium on Computational Geometry},
  year = {2015},
  location = {Eindhoven, The Netherlands},
  numpages = {15},
  keywords = {trajectories, grouping, moving entity, geodesic distance},
  category = {trajectories},
  pages = {674--688},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-939897-83-5},
  issn = {1868-8969},
  volume = {34},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  url = {https://dx.doi.org/10.4230/LIPIcs.SOCG.2015.674},
  doi = {10.4230/LIPIcs.SOCG.2015.674},
}

Mixed Map Labeling

Maarten Löffler, Martin Nöllenburg, Frank Staals

Proc. 9th International Conference on Algorithms and Complexity, 2015

Download Local Copy View Slides Export Citation 
@incollection{mixedmaplabeling2015,
  author = {L{\"o}ffler, Maarten and N{\"o}llenburg, Martin and Staals, Frank},
  title = {Mixed Map Labeling},
  booktitle = {Proc. 9th International Conference on Algorithms and Complexity},
  year = {2015},
  series = {LNCS},
  location = {Paris, France},
  publisher = {Springer},
  url = {https://link.springer.com/10.1007/978-3-319-18173-8_25},
  category = {visualization},
  pages = {339 -- 351},
  url = {https://dx.doi.org/10.1007/978-3-319-18173-8_25},
  doi = {10.1007/978-3-319-18173-8_25},
}

Practical Approaches to Partially Guarding a Polyhedral Terrain

Frank Kammer, Maarten Löffler, Paul Mutser, Frank Staals

Proc. 8th International Conference on Geographic Information Science, 2014

Download Local Copy View Slides Export Citation 
@incollection{siting2014,
  author = {Kammer, Frank and L{\"o}ffler, Maarten and Mutser, Paul and
                 Staals, Frank},
  title = {Practical Approaches to Partially Guarding a Polyhedral Terrain},
  booktitle = {Proc. 8th International Conference on Geographic Information Science},
  year = {2014},
  series = {LNCS},
  volume = {8728},
  url = {https://dx.doi.org/10.1007/978-3-319-11593-1_21},
  doi = {10.1007/978-3-319-11593-1_21},
  location = {Vienna, Austria},
  pages = {318--332},
  numpages = {15},
  publisher = {Springer},
  category = {terrains},
}

Terrain visibility with multiple viewpoints

Ferran Hurtado, Maarten Löffler, Inês Matos, Vera Sacristan, Maria Saumell, Rodrigo Silveira, Frank Staals

Proc. 24th International Symposium on Algorithms and Computation, 2013

Invited for a special issue on ISAAC 2013 in the International Journal on Computational Geometry and its Applications
Download Local Copy View Slides Export Citation 
@incollection{terrainvis2013,
  author = {Hurtado, Ferran and L{\"o}ffler, Maarten and Matos, In{\^e}s and
               Sacristan, Vera and Saumell, Maria and Silveira, Rodrigo and
               Staals, Frank},
  title = {Terrain visibility with multiple viewpoints},
  booktitle = {Proc. 24th International Symposium on
                 Algorithms and Computation},
  series = {LNCS},
  year = {2013},
  location = {Hong Kong, Hong Kong},
  numpages = {11},
  pages = {317--327},
  publisher = {Springer},
  url = {https://dx.doi.org/10.1007/978-3-642-45030-3_30},
  doi = {10.1007/978-3-642-45030-3_30},
  category = {terrains},
  note = {Invited for a special issue on ISAAC 2013 in the International Journal on Computational Geometry and its Applications},
}

Algorithms for Hotspot Computation on Trajectory Data

Joachim Gudmundsson, Marc van Kreveld, Frank Staals

Proc. 21th International Conference on Advances in Geographic Information Systems, 2013

Download Local Copy View Slides Export Citation 
@inproceedings{hotspots2013,
  author = {Gudmundsson, Joachim and van Kreveld, Marc and
                   Staals, Frank},
  title = {Algorithms for Hotspot Computation on Trajectory Data},
  booktitle = {Proc. 21th International Conference on Advances in Geographic
                   Information Systems},
  series = {SIGSPATIAL '13},
  year = {2013},
  location = {Orlando, Florida},
  numpages = {10},
  pages = {134--143},
  url = {https://dl.acm.org/authorize?6976924},
  doi = {10.1145/2525314.2525359},
  publisher = {ACM},
  keywords = {trajectory, moving entity, hotspot, geometric algorithms},
  category = {trajectories},
}

Trajectory Grouping Structure

Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, Frank Staals

Proc. 2013 WADS Algorithms and Data Structures Symposium, 2013

Download Local Copy View Slides Export Citation 
@incollection{grouping2013,
  author = {Buchin, Kevin and Buchin, Maike and
                van Kreveld, Marc and Speckmann, Bettina and Staals, Frank},
  title = {Trajectory Grouping Structure},
  booktitle = {Proc. 2013 WADS Algorithms and Data Structures Symposium},
  series = {LNCS},
  year = {2013},
  volume = {8037},
  location = {London, Ontario, Canada},
  numpages = {12},
  publisher = {Springer},
  pages = {219--230},
  url = {https://dx.doi.org/10.1007/978-3-642-40104-6_19},
  doi = {10.1007/978-3-642-40104-6_19},
  category = {trajectories},
}

Competitive Query Strategies for Minimising the Ply of the Potential Locations of Moving Points

Will Evans, David Kirkpatrick, Maarten Löffler, Frank Staals

Proc. 29th Annual Symposium on Computational Geometry, 2013

Download Local Copy View Slides Export Citation 
@inproceedings{comply2013,
  author = {Evans, Will and Kirkpatrick, David and
                L{\"o}ffler, Maarten and Staals, Frank},
  title = {Competitive Query Strategies for Minimising the Ply of the
                Potential Locations of Moving Points},
  booktitle = {Proc. 29th Annual Symposium on Computational Geometry},
  series = {SoCG '13},
  year = {2013},
  location = {Rio de Janeiro, Brazil},
  numpages = {10},
  publisher = {ACM},
  url = {https://dl.acm.org/authorize?6822815},
  isbn = {978-1-4503-2031-3},
  location = {Rio de Janeiro, Brazil},
  pages = {155--164},
  doi = {10.1145/2462356.2462395},
  keywords = {competitive analysis, input imprecision, kinetic data},
  category = {trajectories},
}

Improved Grid Map Layout by Point Set Matching

David Eppstein, Marc van Kreveld, Bettina Speckmann, Frank Staals

IEEE PacificVis, 2013

Download Local Copy View Slides Export Citation 
@inproceedings{gridmaps2013,
  author = {Eppstein, David and van Kreveld, Marc and Speckmann, Bettina
                  and Staals, Frank},
  title = {Improved Grid Map Layout by Point Set Matching},
  booktitle = {IEEE PacificVis},
  year = {2013},
  publisher = {IEEE},
  pages = {25--32},
  numpages = {8},
  doi = {10.1109/PacificVis.2013.6596124},
  url = {https://dl.doi.org/10.1109/PacificVis.2013.6596124},
  category = {visualization},
}

Segmentation of Trajectories on Non-Monotone Criteria

Boris Aronov, Anne Driemel, Marc van Kreveld, Maarten Löffler, Frank Staals

Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Download Local Copy View Slides Export Citation 
@inproceedings{nonmonotone2013,
  author = {Aronov, Boris and Driemel, Anne and van Kreveld, Marc and
                   L{\"o}ffler, Maarten and Staals, Frank},
  title = {Segmentation of Trajectories on Non-Monotone Criteria},
  booktitle = {Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms},
  year = {2013},
  publisher = {SIAM},
  pages = {1897--1911},
  numpages = {15},
  url = {https://doi.org/10.1137/1.9781611973105.135},
  doi = {10.1137/1.9781611973105.135},
  category = {trajectories},
}

Cinderella versus the Wicked Stepmother

Marijke Bodlaender, Cor Hurkens, Vincent Kusters, Frank Staals, Gerhard Woeginger, Hans Zantema

Theoretical Computer Science, 2012

Download Local Copy View Slides Export Citation 
@incollection{cinderella2012,
  author = {Bodlaender, Marijke and Hurkens, Cor and Kusters, Vincent and
               Staals, Frank and  Woeginger, Gerhard and Zantema, Hans},
  title = {Cinderella versus the Wicked Stepmother},
  year = {2012},
  booktitle = {Theoretical Computer Science},
  series = {LNCS},
  keywords = {cinderella},
  url = {https://dx.doi.org/10.1007/978-3-642-33475-7_5},
  pages = {57--71},
  numpages = {14},
  isbn = {978-3-642-33474-0},
  volume = {7604},
  editor = {Baeten, Jos and Ball, Tom and Boer, Frank},
  doi = {10.1007/978-3-642-33475-7_5},
  publisher = {Springer},
  category = {other},
}

A splitting line model for directional relations

Kevin Buchin, Vincent Kusters, Bettina Speckmann, Frank Staals, Bogdan Vasilescu

Proc. 19th International Conference on Advances in Geographic Information Systems, 2011

Download Local Copy View Slides Export Citation 
@inproceedings{splittingline2011,
  author = {Buchin, Kevin and Kusters, Vincent and Speckmann, Bettina and
                   Staals, Frank and Vasilescu, Bogdan},
  title = {A splitting line model for directional relations},
  booktitle = {Proc. 19th International Conference on Advances in Geographic
                   Information Systems},
  series = {GIS '11},
  year = {2011},
  isbn = {978-1-4503-1031-4},
  location = {Chicago, Illinois},
  pages = {142--151},
  numpages = {10},
  url = {https://dl.acm.org/authorize?6536381},
  doi = {10.1145/2093973.2093994},
  publisher = {ACM},
  keywords = {directional relations, geometric algorithms, splitting line},
  category = {other},
}

Journal Papers

Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Matias Korman, André van Renssen, Marcel Roeloffzen, Frank Staals

SIAM Journal on Discrete Mathemathics, 2023

Download Local Copy View Slides Export Citation 
@article{kinetic_gvd2023,
  author = {Korman, Matias and van Renssen, Andr{\'e} and Roeloffzen, Marcel and Staals, Frank},
  title = {Kinetic Geodesic Voronoi Diagrams in a Simple Polygon},
  journal = {{SIAM} Journal on Discrete Mathemathics},
  volume = {37},
  number = {4},
  pages = {2276--2311},
  year = {2023},
  url = {https://doi.org/10.1137/20m1384804},
  doi = {10.1137/20M1384804},
  project = {kinetic_gvd2020},
  category = {geodesic},
  keywords = {kinetic data structure, simple polygon, geodesic distance, Voronoi diagram},
}

Dynamic Data Structures for \(k\)-Nearest Neighbor Queries

Sarita de Berg, Frank Staals

Computational Geometry, 2023

Special issue on ISAAC 2021
Download Local Copy View Slides Export Citation 
@article{dynamic_knn2022,
  author = {de Berg, Sarita and Staals, Frank},
  title = {Dynamic Data Structures for $k$-Nearest Neighbor Queries},
  journal = {Computational Geometry},
  volume = {111},
  year = {2023},
  doi = {10.1016/j.comgeo.2022.101976},
  url = {https://doi.org/10.1016/j.comgeo.2022.101976},
  keywords = {Data structure, Simple polygon, Geodesic distance, Nearest neighbor searching},
  category = {datastructures},
  project = {dynamic_knn2021},
  note = {Special issue on ISAAC 2021},
}

Covering a set of line segments with a few squares

Joachim Gudmundsson, Mees van de Kerkhof, André van Renssen, Frank Staals, Lionov Wiratma, Sampson Wong

Theoretical Computer Science, 2022

Special issue on CIAC 2021
Download Local Copy View Slides Export Citation 
@article{multihotspots2022,
  author = {Gudmundsson, Joachim  and van de Kerkhof, Mees and van Renssen, Andr{\'e}
                 and Staals, Frank and Wiratma, Lionov and Wong, Sampson},
  title = {Covering a set of line segments with a few squares},
  journal = {Theoretical Computer Science},
  year = {2022},
  publisher = {Elsevier},
  pages = {25},
  doi = {10.1016/j.tcs.2022.04.053},
  url = {https://doi.org/10.1016/j.tcs.2022.04.053},
  category = {trajectories},
  note = {Special issue on CIAC 2021},
  project = {multihotspots2021},
}

Agglomerative Clustering of Growing Squares

Thom Castermans, Bettina Speckmann, Frank Staals, Kevin Verbeek

Algorithmica, 2022

Download Local Copy View Slides Export Citation 
@article{zoomingsquares2022,
  author = {Castermans, Thom and Speckmann, Bettina and Staals, Frank
                 and Verbeek, Kevin},
  title = {Agglomerative Clustering of Growing Squares},
  journal = {Algorithmica},
  volume = {84},
  number = {1},
  pages = {216--233},
  year = {2022},
  numpages = {18},
  publisher = {Springer},
  category = {datastructures},
  keywords = {kinetic data structures},
  url = {https://doi.org/10.1007/s00453-021-00873-0},
  doi = {10.1007/s00453-021-00873-0},
  project = {zoomingsquares2018},
}

Maximum Physically Consistent Trajectories

Bram Custers, Mees van de Kerkhof, Wouter Meulemans, Bettina Speckmann, Frank Staals

ACM Transactions on Spatial Algorithms Systems, 2021

Download Local Copy View Slides Export Citation 
@article{trajectoryoutliers2021,
  author = {Custers, Bram and van de Kerkhof, Mees and Meulemans, Wouter and
                 Speckmann, Bettina and Staals, Frank},
  title = {Maximum Physically Consistent Trajectories},
  journal = {{ACM} Transactions on Spatial Algorithms Systems},
  volume = {7},
  number = {4},
  pages = {17:1--17:33},
  year = {2021},
  numpages = {33},
  category = {trajectories},
  url = {https://doi.org/10.1145/3452378},
  doi = {10.1145/3452378},
  project = {trajectoryoutliers2019},
}

Convexity-Increasing Morphs of Planar Graphs

Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals, Darren Strash

Computational Geometry: Theory and Applications, 2019

Special issue on EuroCG 2018.
Download Local Copy View Slides Export Citation 
@article{convexmorphing2019,
  author = {Kleist, Linda and Klemz, Boris and Lubiw, Anna and Schlipf, Lena
                 and Staals, Frank and Strash, Darren},
  title = {Convexity-Increasing Morphs of Planar Graphs},
  journal = {Computational Geometry: Theory and Applications},
  year = {2019},
  publisher = {Elsevier},
  project = {convexmorphing2018},
  note = {Special issue on EuroCG 2018.},
  doi = {j.comgeo.2019.07.007},
  pages = {69 -- 88},
  issn = {0925-7721},
  volume = {84},
  url = {https://doi.org/10.1016/j.comgeo.2019.07.007},
  category = {graphs},
  keywords = {planar graphs, graph drawing},
}

Computing the Expected Value and Variance of Geometric Measures

Constantinos Tsirogiannis, Frank Staals, Vincent Pellissier

Journal of Experimental Algorithmics, 2018

Special issue on ALENEX 2017
Download Local Copy View Slides Export Citation 
@article{expected_measures2018,
  author = {Tsirogiannis, Constantinos and Staals, Frank and Pellissier, Vincent},
  title = {Computing the Expected Value and Variance of Geometric Measures},
  journal = {Journal of Experimental Algorithmics},
  issue_date = {July 2018},
  volume = {23},
  number = {2},
  month = {jul},
  year = {2018},
  issn = {1084-6654},
  pages = {2.4:1--2.4:32},
  articleno = {2.4},
  numpages = {32},
  url = {https://dx.doi.org/10.1145/3228331},
  doi = {10.1145/3228331},
  publisher = {ACM},
  project = {expected_measures2017},
  category = {other},
  keywords = {Stochastic point-sets, computational geometry, descriptive statistics},
  note = {Special issue on ALENEX 2017},
}

A Refined Definition for Groups of Moving Entities and its Computation

Marc van Kreveld, Maarten Löffler, Frank Staals, Lionov Wiratma

International Journal of Computational Geometry & Applications, 2018

Special Issue on ISAAC 2016.
Download Local Copy View Slides Export Citation 
@article{refined_grouping2018,
  author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank and
                 Wiratma, Lionov},
  title = {A Refined Definition for Groups of Moving Entities and its Computation},
  journal = {International Journal of Computational Geometry \& Applications},
  category = {trajectories},
  project = {refined_grouping2016},
  year = {2018},
  volume = {28},
  number = {02},
  pages = {181--196},
  url = {https://dx.doi.org/10.1142/S0218195918600051},
  doi = {10.1142/S0218195918600051},
  note = {Special Issue on ISAAC 2016.},
}

Central Trajectories

Marc Van Kreveld, Maarten Löffler, Frank Staals

Journal of Computational Geometry, 2017

Download Local Copy View Slides Export Citation 
@article{central2017,
  author = {Van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank},
  title = {Central Trajectories},
  journal = {Journal of Computational Geometry},
  category = {trajectories},
  year = {2017},
  doi = {10.20382/jocg.v8i1a14},
  url = {https://dx.doi.org/10.20382/jocg.v8i1a14},
  pages = {366--386},
  numpages = {21},
  volume = {8},
  number = {1},
}

On the complexity of minimum-link path problems

Irina Kostitsyna, Maarten Löffler, Frank Staals, Valentin Polishchuk

Journal of Computational Geometry, 2017

Special issue on SoCG 2016
Download Local Copy View Slides Export Citation 
@article{minlinkpath2017,
  author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                 and Polishchuk, Valentin},
  title = {On the complexity of minimum-link path problems},
  journal = {Journal of Computational Geometry},
  category = {terrains},
  year = {2017},
  doi = {10.20382/jocg.v8i2},
  url = {https://dx.doi.org/10.20382/jocg.v8i2},
  pages = {80--108},
  numpages = {29},
  volume = {8},
  number = {2},
  note = {Special issue on SoCG 2016},
  project = {minlinkpath2016},
}

Mixed Map Labeling

Maarten Löffler, Martin Nöllenburg, Frank Staals

Journal of Spatial Information Science, 2016

Download Local Copy View Slides Export Citation 
@article{mixedmaplabeling2016,
  author = {L{\"o}ffler, Maarten and N{\"o}llenburg, Martin and Staals, Frank},
  title = {Mixed Map Labeling},
  journal = {Journal of Spatial Information Science},
  year = {2016},
  volume = {13},
  pages = {3--32},
  numpages = {30},
  doi = {10.5311/JOSIS.2016.13.264},
  category = {visualization},
  project = {mixedmaplabeling2015},
  url = {https://dx.doi.org/10.5311/JOSIS.2016.13.264},
}

Multi-Granular Trend Detection for Time-Series Analysis

Arthur van Goethem, Frank Staals, Maarten Löffler, Jason Dykes, Bettina Speckmann

IEEE Transactions on Visualization and Computer Graphics, 2016

Presented at InfoVis 2016.
Download Local Copy View Slides Export Citation 
@article{ensembles2016,
  author = {van Goethem, Arthur and Staals, Frank and L{\"o}ffler, Maarten
                 and Dykes, Jason and Speckmann, Bettina},
  title = {Multi-Granular Trend Detection for Time-Series Analysis},
  journal = {IEEE Transactions on Visualization and Computer Graphics},
  volume = {23},
  number = {1},
  pages = {661--670},
  doi = {10.1109/TVCG.2016.2598619},
  issn = {1077-2626},
  publisher = {IEEE},
  year = {2016},
  location = {Baltimore, Maryland, USA},
  numpages = {10},
  keywords = {ensemble, time-series, trend detection, trajectories, grouping,
                 visualization},
  category = {visualization},
  doi = {10.1109/TVCG.2016.2598619},
  url = {https://dx.doi.org/10.1109/TVCG.2016.2598619},
  note = {Presented at InfoVis 2016.},
}

Minimizing Co-location Potential of Moving Entities

Will Evans, David Kirkpatrick, Maarten Löffler, Frank Staals

SIAM Journal on Computing, 2016

Download Local Copy View Slides Export Citation 
@article{comply2016,
  author = {Evans, Will and Kirkpatrick, David and
                L{\"o}ffler, Maarten and Staals, Frank},
  title = {Minimizing Co-location Potential of Moving Entities},
  journal = {SIAM Journal on Computing},
  volume = {45},
  number = {5},
  pages = {1870--1893},
  year = {2016},
  doi = {10.1137/15M1031217},
  url = {https://dx.doi.org/10.1137/15M1031217},
  category = {trajectories},
  project = {comply2013},
}

Improved Grid Map Layout by Point Set Matching

David Eppstein, Marc van Kreveld, Bettina Speckmann, Frank Staals

International Journal of Computational Geometry & Applications, 2015

Download Local Copy View Slides Export Citation 
@article{pointset_gridmap2015,
  author = {Eppstein, David and van Kreveld, Marc and Speckmann, Bettina
                 and Staals, Frank},
  title = {Improved Grid Map Layout by Point Set Matching},
  journal = {International Journal of Computational Geometry \& Applications},
  publisher = {World Scientific},
  category = {visualization},
  project = {gridmaps2013},
  year = {2015},
  volume = {25},
  number = {2},
  doi = {10.1142/S0218195915500077},
  url = {https://dx.doi.org/10.1142/S0218195915500077},
}

Trajectory Grouping Structure

Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, Frank Staals

Journal of Computational Geometry, 2015

Download Local Copy View Slides Export Citation 
@article{grouping2015,
  author = {Buchin, Kevin and Buchin, Maike and
                van Kreveld, Marc and Speckmann, Bettina and Staals, Frank},
  title = {Trajectory Grouping Structure},
  journal = {Journal of Computational Geometry},
  category = {trajectories},
  year = {2015},
  project = {grouping2013},
  volume = {6},
  number = {1},
  doi = {10.20382/jocg.v6i1a3},
  url = {https://dx.doi.org/10.20382/jocg.v6i1a3},
}

Terrain visibility with multiple viewpoints

Ferran Hurtado, Maarten Löffler, Inês Matos, Vera Sacristan, Maria Saumell, Rodrigo Silveira, Frank Staals

International Journal of Computational Geometry & Applications, 2014

Special Issue on ISAAC 2013.
Download Local Copy View Slides Export Citation 
@article{terrainvis2014,
  author = {Hurtado, Ferran and L{\"o}ffler, Maarten and Matos, In{\^e}s and
                 Sacristan, Vera and Saumell, Maria and Silveira, Rodrigo and
                 Staals, Frank},
  title = {Terrain visibility with multiple viewpoints},
  journal = {International Journal of Computational Geometry \& Applications},
  publisher = {World Scientific},
  category = {terrains},
  note = {Special Issue on ISAAC 2013.},
  year = {2014},
  volume = {24},
  number = {04},
  pages = {275--306},
  doi = {10.1142/S0218195914600085},
  url = {https://dx.doi.org/10.1142/S0218195914600085},
  project = {terrainvis2013},
}

Segmentation of Trajectories on Non-Monotone Criteria

Boris Aronov, Anne Driemel, Marc van Kreveld, Maarten Löffler, Frank Staals

Transactions on Algorithms, 2014

Download Local Copy View Slides Export Citation 
@article{nonmonotone2014,
  author = {Aronov, Boris and Driemel, Anne and van Kreveld, Marc and
                    L{\"o}ffler, Maarten and Staals, Frank},
  title = {Segmentation of Trajectories on Non-Monotone Criteria},
  journal = {Transactions on Algorithms},
  publisher = {ACM},
  category = {trajectories},
  project = {nonmonotone2013},
  year = {2014},
  url = {https://dl.acm.org/authorize?N08347},
  issue_date = {December 2015},
  volume = {12},
  number = {2},
  month = {12},
  issn = {1549-6325},
  pages = {26:1--26:28},
  articleno = {26},
  numpages = {28},
  doi = {10.1145/2660772},
  address = {New York, NY, USA},
  keywords = {Trajectory, dynamic programming, geometric algorithms, segmentation},
  project = {nonmonotone2013},
}

The Connect-The-Dots Family of Puzzles: Design and Automatic Generation

Maarten Löffler, Mira Kaiser, Tim van Kapel, Gerwin Klappe, Marc van Kreveld, Frank Staals

ACM Transactions on Graphics, 2014

Presented at SigGraph 2014.
Download Local Copy View Slides Export Citation 
@article{pointpuzzles2014,
  author = {L{\"o}ffler, Maarten and Kaiser, Mira and
                  van Kapel, Tim and Klappe, Gerwin and
                  van Kreveld, Marc and Staals, Frank},
  title = {The Connect-The-Dots Family of Puzzles: Design and Automatic Generation},
  journal = {ACM Transactions on Graphics},
  issue_date = {July 2014},
  volume = {33},
  number = {4},
  month = {jul},
  year = {2014},
  issn = {0730-0301},
  pages = {72:1--72:10},
  numpages = {10},
  doi = {10.1145/2601097.2601224},
  publisher = {ACM},
  address = {New York, NY, USA},
  keywords = {algorithms, geometry, pencil-and-paper puzzles},
  category = {other},
  url = {https://dl.acm.org/authorize?N95144},
  note = {Presented at SigGraph 2014.},
}

Workshop Abstracts

Robust Bichromatic Classification using Two Lines

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, Frank Staals

Abstr. 40th European Workshop on Computational Geometry (EuroCG), 2024

Download Local Copy View Slides Export Citation 
@article{twolineseparator_eurocg,
  author = {Glazenburg, Erwin and van der Horst, Thijs and Peters, Tom and Speckmann, Bettina and Staals, Frank},
  title = {Robust Bichromatic Classification using Two Lines},
  journal = {Abstr. 40th European Workshop on Computational Geometry (EuroCG)},
  year = {2024},
  location = {Ioannina, Greece},
  numpages = {6},
  category = {classification},
  project = {twolineseparator2024},
}

Exact solutions to the Weighted Region Problem

Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira, Frank Staals

Abstr. 40th European Workshop on Computational Geometry (EuroCG), 2024

Download Local Copy View Slides Export Citation 
@article{wrp_eurocg,
  author = {de Berg, Sarita and Esteban, Guillermo and I. Silveira, Rodrigo and Staals, Frank},
  title = {Exact solutions to the Weighted Region Problem},
  journal = {Abstr. 40th European Workshop on Computational Geometry (EuroCG)},
  year = {2024},
  location = {Ioannina, Greece},
  numpages = {8},
  category = {wrp},
  project = {wrp2024},
}

The Complexity of Geodesic Spanners using Steiner Points

Sarita de Berg, Tim Ophelders, Irene Parada, Frank Staals, Jules Wulms

Abstr. 40th European Workshop on Computational Geometry (EuroCG), 2024

Download Local Copy View Slides Export Citation 
@article{steiner_spanners_eurocg,
  author = {de Berg, Sarita and Ophelders, Tim and Parada, Irene and Staals, Frank and Wulms, Jules},
  title = {The Complexity of Geodesic Spanners using Steiner Points},
  journal = {Abstr. 40th European Workshop on Computational Geometry (EuroCG)},
  year = {2024},
  location = {Ioannina, Greece},
  numpages = {7},
  category = {geodesic},
  project = {steinerspanners2024},
}

Classification of bichromatic points with outliers

Erwin Glazenburg, Marc Kreveld, Frank Staals

Abstr. 39th European Workshop on Computational Geometry (EuroCG), 2023

Download Local Copy View Slides Export Citation 
@article{dynamicsvm_eurocg,
  author = {Glazenburg, Erwin and Kreveld, Marc and Staals, Frank},
  title = {Classification of bichromatic points with outliers},
  journal = {Abstr. 39th European Workshop on Computational Geometry (EuroCG)},
  year = {2023},
  location = {Barcelona, Spain},
  numpages = {8},
  category = {algorithms},
  project = {dynamicsvm2024},
}

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain

Sarita de Berg, Till Miltzow, Frank Staals

Abstr. 39th European Workshop on Computational Geometry (EuroCG), 2023

Download Local Copy View Slides Export Citation 
@article{twoptsp_eurocg,
  author = {de Berg, Sarita and Miltzow, Till and Staals, Frank},
  title = {Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain},
  journal = {Abstr. 39th European Workshop on Computational Geometry (EuroCG)},
  year = {2023},
  location = {Barcelona, Spain},
  numpages = {9},
  category = {geodesic},
  project = {twoptsp2024},
}

Segment Visibility Counting Queries in Polygons

Kevin Buchin, Custers Bram, Ivor Hoog van der, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, Frank Staals

Abstr. 38th European Workshop on Computational Geometry (EuroCG), 2022

Download Local Copy View Slides Export Citation 
@article{segmentvis_eurocg,
  author = {Buchin, Kevin and Bram, Custers and Hoog van der, Ivor and
                 L{\"o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel
                 and  Staals, Frank},
  title = {Segment Visibility Counting Queries in Polygons},
  journal = {Abstr. 38th European Workshop on Computational Geometry (EuroCG)},
  year = {2022},
  location = {Perugia, Italy},
  numpages = {8},
  category = {datastructures},
}

Querying the Hausdorff Distance of a Line Segment

Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen

Abstr. 38th European Workshop on Computational Geometry (EuroCG), 2022

Download Local Copy View Slides Export Citation 
@article{dynamic_hausdorff_eurocg,
  author = {Staals, Frank and Urhausen, J{\'e}r{\^o}me
                 and Vermeulen, Jordi L.},
  title = {Querying the Hausdorff Distance of a Line Segment},
  journal = {Abstr. 38th European Workshop on Computational Geometry (EuroCG)},
  year = {2022},
  location = {Perugia, Italy},
  numpages = {8},
  category = {datastructures},
}

The complexity of geodesic spanners

Sarita de Berg, Marc van Kreveld, Frank Staals

Abstr. 38th European Workshop on Computational Geometry (EuroCG), 2022

Download Local Copy View Slides Export Citation 
@article{spanners_eurocg,
  author = {de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
  title = {The complexity of geodesic spanners},
  journal = {Abstr. 38th European Workshop on Computational Geometry (EuroCG)},
  year = {2022},
  location = {Perugia, Italy},
  numpages = {7},
  category = {geodesic},
  project = {geodesic_spanners2023},
}

A Dynamic Data Structure for \(k\)-Nearest Neighbors Queries

Sarita de Berg, Frank Staals

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

Download Local Copy View Slides Export Citation 
@article{dynamic_knn_eurocg,
  author = {de Berg, Sarita and Staals, Frank},
  title = {A Dynamic Data Structure for $k$-Nearest Neighbors Queries},
  journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
  year = {2021},
  location = {St. Petersburg, Russia (online)},
  numpages = {7},
  category = {datastructures},
  url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_14.pdf},
  project = {dynamic_knn2021},
}

Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Ivor Hoog van der, Mees van der Kerkhof, Marc van Kreveld, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

Download Local Copy View Slides Export Citation 
@article{pixelpolygons_eurocg,
  author = {Hoog van der, Ivor and van der Kerkhof, Mees and van Kreveld, Marc and
                 L{\"o}ffler, Maarten and Staals, Frank and Urhausen, J{\'e}r{\^o}me
                 and Vermeulen, Jordi L.},
  title = {Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance},
  journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
  year = {2021},
  location = {St. Petersburg, Russia (online)},
  numpages = {7},
  category = {other},
  project = {pixelpolygons2021},
  url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_13.pdf},
}

Shortest Paths in Portalgons

Maarten Löffler, Rodrigo I. Silveira, Frank Staals

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

Download Local Copy View Slides Export Citation 
@article{portalgons_eurocg,
  author = {L{\"o}ffler, Maarten and I. Silveira, Rodrigo and Staals, Frank},
  title = {Shortest Paths in Portalgons},
  journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
  year = {2021},
  location = {St. Petersburg, Russia (online)},
  numpages = {7},
  category = {other},
  url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_31.pdf},
  project = {portalgons2023},
}

Terrain prickliness: theoretical grounds for low complexity viewsheds

Ankush Acharyya, Ramesh Jallu, Maarten Löffler, Gert Meijer, Maria Saumell, Rodrigo I. Silveira, Frank Staals, Hans Raj Tiwary

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

Download Local Copy View Slides Export Citation 
@article{prickliness_eurocg,
  author = {Acharyya, Ankush and Jallu, Ramesh and  L{\"o}ffler, Maarten and
                 Meijer, Gert and Saumell, Maria and I. Silveira, Rodrigo and
                 Staals, Frank and Raj Tiwary, Hans},
  title = {Terrain prickliness: theoretical grounds for low complexity viewsheds},
  journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
  year = {2021},
  location = {St. Petersburg, Russia (online)},
  numpages = {7},
  category = {terrains},
  url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_34.pdf},
  project = {prickliness2021},
}

Improved Map Construction using Subtrajectory Clustering

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Jorren Hendriks, Erfan Hosseini Sereshgi, Vera Sacristan, Rodrigo I. Silveira, Jorrick Sleijster, Frank Staals, Carola Wenk

Abstr. 4th ACM SIGSPATIAL Workshop on Location-based Recommendations, Geosocial Networks and Geoadvertising (LocalRec), 2020

Download Local Copy View Slides Export Citation 
@article{improved_bundles2020,
  author = {Buchin, Kevin and Buchin, Maike and  Gudmundsson, Joachim and
                 Hendriks, Jorren and Hosseini Sereshgi, Erfan and
                 Sacristan, Vera and I. Silveira, Rodrigo and Sleijster, Jorrick and
                 Staals, Frank and Wenk, Carola },
  title = {Improved Map Construction using Subtrajectory Clustering},
  journal = {Abstr. 4th ACM SIGSPATIAL Workshop on Location-based Recommendations,
                 Geosocial Networks and Geoadvertising (LocalRec)},
  year = {2020},
  location = {Seattle, Washington, USA (online)},
  numpages = {4},
  category = {trajectories},
  project = {bundles2017},
  doi = {10.1145/3423334.3431451},
  url = {https://dl.acm.org/doi/10.1145/3423334.3431451?cid=81493660306},
}

Improved space bounds for Fréchet distance queries

Buchin Maike, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, Frank Staals

Abstr. 36th European Workshop on Computational Geometry (EuroCG), 2020

Download Local Copy View Slides Export Citation 
@article{frechet_datastructures_eurocg,
  author = {Maike, Buchin and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and
                 I. Silveira, Rodrigo and Staals, Frank},
  title = {Improved space bounds for Fréchet distance queries},
  journal = {Abstr. 36th European Workshop on Computational Geometry (EuroCG)},
  year = {2020},
  location = {Wurzburg, Germany (online)},
  numpages = {7},
  category = {trajectories},
  url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_65.pdf},
  project = {frechet_segmentqueries2022},
}

Covering a set of line segments with a few squares

Joachim Gudmundsson, Mees van de Kerkhof, André van Renssen, Frank Staals, Lionov Wiratma, Sampson Wong

Abstr. 36th European Workshop on Computational Geometry (EuroCG), 2020

Download Local Copy View Slides Export Citation 
@article{multihotspots_eurocg,
  author = {Gudmundsson, Joachim  and van de Kerkhof, Mees and van Renssen, Andr{\'e} and
                 Staals, Frank and Wiratma, Lionov and Wong, Sampson},
  title = {Covering a set of line segments with a few squares},
  journal = {Abstr. 36th European Workshop on Computational Geometry (EuroCG)},
  year = {2020},
  location = {Wurzburg, Germany (online)},
  numpages = {8},
  category = {trajectories},
  project = {multihotspots2021},
  url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_45.pdf},
}

Maximum Physically Consistent Trajectories

Custers Bram, Mees van de Kerkhof, Wouter Meulemans, Bettina Speckmann, Frank Staals

Abstr. 35th European Workshop on Computational Geometry (EuroCG), 2019

Download Local Copy View Slides Export Citation 
@article{trajectoryoutlierdetection_eurocg,
  author = {Bram, Custers and van de Kerkhof, Mees and Meulemans, Wouter and
                 Speckmann, Bettina and Staals, Frank},
  title = {Maximum Physically Consistent Trajectories},
  journal = {Abstr. 35th European Workshop on Computational Geometry (EuroCG)},
  year = {2019},
  location = {Utrecht, The Netherlands},
  numpages = {6},
  category = {trajectories},
  url = {http://www.eurocg2019.uu.nl/papers/44.pdf},
  project = {trajectoryoutliers2019},
}

Approximating the Earth Mover’s Distance between a set of points and line segments

Marc van Kreveld, Frank Staals, Amir Vaxman, Jordi L. Vermeulen

Abstr. 35th European Workshop on Computational Geometry (EuroCG), 2019

Download Local Copy View Slides Export Citation 
@article{emd_eurocg,
  author = {van Kreveld, Marc and Staals, Frank and Vaxman, Amir and Vermeulen, Jordi L.},
  title = {Approximating the Earth Mover's Distance between a set of points and line segments},
  journal = {Abstr. 35th European Workshop on Computational Geometry (EuroCG)},
  year = {2019},
  location = {Utrecht, The Netherlands},
  numpages = {6},
  category = {other},
  url = {http://www.eurocg2019.uu.nl/papers/24.pdf},
  project = {emd2021},
}

Convexity-Increasing Morphs of Planar Graphs

Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals, Darren Strash

Abstr. 34th European Workshop on Computational Geometry (EuroCG), 2018

Invited for a special issue on EuroCG 2018 in Computational Geometry Theory and Applications.
Download Local Copy View Slides Export Citation 
@article{convexmorphing2018_eurocg,
  author = {Kleist, Linda and Klemz, Boris and Lubiw, Anna and Schlipf, Lena
                 and Staals, Frank and Strash, Darren},
  title = {Convexity-Increasing Morphs of Planar Graphs},
  journal = {Abstr. 34th European Workshop on Computational Geometry (EuroCG)},
  year = {2018},
  location = {Berlin, Germany},
  numpages = {6},
  category = {graphs},
  keywords = {planar graphs, graph drawing},
  note = {Invited for a special issue on EuroCG 2018 in Computational Geometry Theory and Applications.},
  project = {convexmorphing2018},
  url = {https://conference.imp.fu-berlin.de/eurocg18/download/eurocg_proc.pdf},
}

Agglomerative Clustering of Growing Squares

Thom Castermans, Bettina, Speckmann, Frank Staals, Kevin Verbeek

Abstr. 34th European Workshop on Computational Geometry (EuroCG), 2017

Download Local Copy View Slides Export Citation 
@article{zoomingsquares2018_eurocg,
  author = {Castermans, Thom and Speckmann, Bettina, and Staals, Frank
                 and Verbeek, Kevin},
  title = {Agglomerative Clustering of Growing Squares},
  journal = {Abstr. 34th European Workshop on Computational Geometry (EuroCG)},
  year = {2017},
  location = {Berlin, Germany},
  numpages = {6},
  category = {datastructures},
  project = {zoomingsquares2018},
  keywords = {kinetic data structures},
  url = {https://conference.imp.fu-berlin.de/eurocg18/download/eurocg_proc.pdf},
}

Kinetic All-Pairs Shortest Path in a Simple Polygon

Yago Diez, Matias, Korman, André van Renssen, Marcel Roeloffzen, Frank Staals

Abstr. 33th European Workshop on Computational Geometry (EuroCG), 2017

Download Local Copy View Slides Export Citation 
@article{all_pair_kinetic_geodesics2017,
  author = {Diez, Yago and Korman, Matias, and van Renssen, Andr{\'e} and Roeloffzen, Marcel
                 and Staals, Frank},
  title = {Kinetic All-Pairs Shortest Path in a Simple Polygon},
  journal = {Abstr. 33th European Workshop on Computational Geometry (EuroCG)},
  year = {2017},
  location = {Malm{\"o}, Sweden},
  numpages = {4},
  category = {geodesic},
  url = {http://csconferences.mah.se/eurocg2017/proceedings.pdf},
}

Computing the Expected Area of an Induced Triangle

Vissarion Fisikopoulos, Frank Staals, Constantinos Tsirogiannis

Abstr. 4th Computational Geometry Young Researchers Forum (CG:YRF), 2016

Download Local Copy View Slides Export Citation 
@article{expected_triangle_area2016,
  author = {Fisikopoulos, Vissarion and Staals, Frank and Tsirogiannis, Constantinos},
  title = {Computing the Expected Area of an Induced Triangle},
  journal = {Abstr. 4th Computational Geometry Young Researchers Forum (CG:YRF)},
  year = {2016},
  location = {Boston, USA},
  numpages = {2},
  category = {other},
  project = {expected_measures2017},
  url = {http://computational-geometry.org/YRF/cgyrf2016.pdf},
}

A Refined Definition for Groups of Moving Entities and its Computation

Marc van Kreveld, Maarten Löffler, Frank Staals, Lionov Wiratma

Abstr. 32th European Workshop on Computational Geometry (EuroCG), 2016

Download Local Copy View Slides Export Citation 
@article{new_grouping_eurocg2016,
  author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank and
                 Wiratma, Lionov},
  title = {A Refined Definition for Groups of Moving Entities and its Computation},
  journal = {Abstr. 32th European Workshop on Computational Geometry (EuroCG)},
  year = {2016},
  location = {Lugano, Switzerland},
  numpages = {4},
  category = {trajectories},
  project = {refined_grouping2016},
  url = {http://www.eurocg2016.usi.ch/sites/default/files/paper_67.pdf},
}

New Results on Trajectory Grouping under Geodesic Distance

Maarten Löffler, Frank Staals, Jérôme Urhausen

Abstr. 32th European Workshop on Computational Geometry (EuroCG), 2016

Download Local Copy View Slides Export Citation 
@article{geodesic_extras_eurocg2016,
  author = {L{\"o}ffler, Maarten and Staals, Frank and Urhausen, J{\'e}r{\^o}me},
  title = {New Results on Trajectory Grouping under Geodesic Distance},
  journal = {Abstr. 32th European Workshop on Computational Geometry (EuroCG)},
  year = {2016},
  location = {Lugano, Switzerland},
  numpages = {4},
  category = {trajectories},
  project = {geogrouping2015},
  url = {http://www.eurocg2016.usi.ch/sites/default/files/paper_70.pdf},
}

Grouping Time-varying Data for Interactive Exploration

Arthur van Goethem, Marc Van Kreveld, Maarten Löffler, Bettina Speckmann, Frank Staals

Abstr. 32th European Workshop on Computational Geometry (EuroCG), 2016

Download Local Copy View Slides Export Citation 
@article{cake_eurocg2016,
  author = {van Goethem, Arthur and Van Kreveld, Marc and L{\"o}ffler, Maarten
                 and Speckmann, Bettina and Staals, Frank},
  title = {Grouping Time-varying Data for Interactive Exploration},
  journal = {Abstr. 32th European Workshop on Computational Geometry (EuroCG)},
  year = {2016},
  location = {Lugano, Switzerland},
  numpages = {4},
  category = {trajectories},
  project = {cake2016},
  url = {http://www.eurocg2016.usi.ch/sites/default/files/paper_48.pdf},
}

On the complexity of minimum-link path problems

Irina Kostitsyna, Maarten Löffler, Frank Staals, Valentin Polishchuk

Abstr. XVI Spanish Meeting on Computational Geometry, 2015

Download Local Copy View Slides Export Citation 
@article{minlinkpath_spanishcg2015,
  author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                 and Polishchuk, Valentin},
  title = {On the complexity of minimum-link path problems},
  journal = {Abstr. XVI Spanish Meeting on Computational Geometry},
  year = {2015},
  location = {Barcelona, Spain},
  numpages = {4},
  pages = {21 -- 24},
  url = {http://www-ma2.upc.es/egc15/wp-content/uploads/2013/10/AbstractsXVIEGC.pdf},
  category = {terrains},
  project = {minlinkpath2016},
}

Central Trajectories

Marc Van Kreveld, Maarten Löffler, Frank Staals

Abstr. 31th European Workshop on Computational Geometry (EuroCG), 2015

Download Local Copy View Slides Export Citation 
@article{central_eurocg2015,
  author = {Van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank},
  title = {Central Trajectories},
  journal = {Abstr. 31th European Workshop on Computational Geometry (EuroCG)},
  year = {2015},
  location = {Ljubljana, Slovenia},
  numpages = {4},
  pages = {129 -- 132},
  url = {http://eurocg15.fri.uni-lj.si/pub/eurocg15-book-of-abstracts.pdf},
  category = {trajectories},
  project = {central2017},
}

Homotopy Measures for Representative Trajectories

Chambers Erin, Irina Kostitsyna, Maarten Löffler, Frank Staals

Abstr. 31th European Workshop on Computational Geometry (EuroCG), 2015

Download Local Copy View Slides Export Citation 
@article{homotopymeasures_eurocg2015,
  author = {Chambers Erin and Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank},
  title = {Homotopy Measures for Representative Trajectories},
  journal = {Abstr. 31th European Workshop on Computational Geometry (EuroCG)},
  year = {2015},
  location = {Ljubljana, Slovenia},
  numpages = {4},
  pages = {125 -- 128},
  url = {http://eurocg15.fri.uni-lj.si/pub/eurocg15-book-of-abstracts.pdf},
  category = {trajectories},
  project = {homotopymeasures2016},
}

Query Strategies for Minimizing the Ply of the Potential Locations of Entities Moving with Different Speeds

Will Evans, David Kirkpatrick, Maarten Löffler, Frank Staals

Abstr. 30th European Workshop on Computational Geometry (EuroCG), 2014

Download Local Copy View Slides Export Citation 
@article{colored_comply2014,
  author = {Evans, Will and Kirkpatrick, David and
                 L{\"o}ffler, Maarten and Staals, Frank},
  title = {Query Strategies for Minimizing the Ply of the
                 Potential Locations of Entities Moving with Different Speeds},
  journal = {Abstr. 30th European Workshop on Computational Geometry (EuroCG)},
  year = {2014},
  location = {Ein-Gedi, Israel},
  numpages = {4},
  url = {http://www.cs.bgu.ac.il/~eurocg14/papers/paper_24.pdf},
  category = {trajectories},
  project = {comply2013},
}

Clear Unit-Distance Graphs

Marc van Kreveld, Maarten Löffler, Frank Staals

Abstr. 29th European Workshop on Computational Geometry (EuroCG), 2013

Download Local Copy View Slides Export Citation 
@article{clear_unit-distance_graphs_connect_the_dot2013,
  author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank},
  title = {Clear Unit-Distance Graphs},
  journal = {Abstr. 29th European Workshop on Computational Geometry (EuroCG)},
  year = {2013},
  location = {Braunschweig, Germany},
  numpages = {4},
  url = {http://www.ibr.cs.tu-bs.de/alg/eurocg13/booklet_eurocg13.pdf},
  project = {pointpuzzles2014},
  category = {other},
}

One-to-one Point Set Matchings for Grid Map Layout

David Eppstein, Marc van Kreveld, Bettina Speckmann, Frank Staals

Abstr. 28th European Workshop on Computational Geometry (EuroCG), 2012

Download Local Copy View Slides Export Citation 
@article{pointset_gridmap2012,
  author = {Eppstein, David and van Kreveld, Marc and Speckmann, Bettina
                 and Staals, Frank},
  title = {One-to-one Point Set Matchings for Grid Map Layout},
  journal = {Abstr. 28th European Workshop on Computational Geometry (EuroCG)},
  year = {2012},
  location = {Assisi, Italy},
  numpages = {4},
  url = {http://www.diei.unipg.it/eurocg2012/booklet.pdf},
  category = {visualization},
  project = {gridmaps2013},
}

Theses

Geographic Grid Embeddings

Frank Staals

Eindhoven University of Technology, 2011

Download Local Copy View Slides Export Citation 
@mastersthesis{geographic_grid_embeddings2011,
  author = {Staals, Frank},
  title = {Geographic Grid Embeddings},
  institution = {Eindhoven University of Technology},
  school = {Eindhoven University of Technology},
  year = {2011},
  url = {https://alexandria.tue.nl/extra1/afstversl/wsk-i/staals2011.pdf},
  urldate = {2012-02-05},
  supervisor = {Speckmann, Bettina},
  category = {visualization},
  project = {gridmaps2013},
}

Technical Reports

Approximating the Earth Mover’s Distance between a set of points and line segments

Marc van Kreveld, Frank Staals, Amir Vaxman, Jordi L. Vermeulen

CoRR, 2021

Download Local Copy View Slides Export Citation 
@article{emd2021,
  author = {van Kreveld, Marc and Staals, Frank and Vaxman, Amir and Vermeulen, Jordi L.},
  title = {Approximating the Earth Mover's Distance between a set of points and line segments},
  year = {2021},
  category = {other},
  journal = {CoRR},
  volume = {abs/2104.08136},
  url = {https://arxiv.org/abs/2104.08136},
}