Visibility Queries in Simple Polygons

Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla, Yakov Nekrich, Eunjin Oh, André van Renssen, Frank Staals, Haitao Wang, Jie Xue

Proc. 53thEATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2026

To Appear

Download Local Copy View Slides Export Citation

@inproceedings{visibilityqueries2026,
  author = {Bhore, Sujoy and  Liu, Chih-Hung and  Murty Naredla, Anurag  and
                 Nekrich, Yakov and  Oh, Eunjin and  van Renssen, André  and
                 Staals, Frank and  Wang, Haitao and  Xue, Jie},
  title = {Visibility Queries in Simple Polygons},
  booktitle = {Proc. 53thEATCS International Colloquium on Automata, Languages, and Programming (ICALP)},
  year = {2026},
  location = {London, United Kingdom},
  keywords = {data structure, simple polygon, visibility},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  note = {To Appear},
}

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, Meirav Zehavi

Proc. 20th Scandinavian Symposium and Workshops on Algorithm Theory, 2026

To Appear

Download Local Copy View Slides Export Citation

@inproceedings{unitdiskclique2026,
  author = {Gao, Jie and Gawrychowski, Paweł and Giannopoulos, Panos and Mulzer, Wolfgang
                and Singh, Satyam and Staals, Frank and Zehavi, Meirav},
  title = {Near-Linear and Parameterized Approximations for Maximum Cliques
                 in Disk Graphs},
  booktitle = {Proc. 20th Scandinavian Symposium and Workshops on Algorithm Theory},
  year = {2026},
  location = {Copenhagen, Denmark},
  keywords = {data structure, disk graph, clique},
  category = {other},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  note = {To Appear},
}

Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Joost van der Laan, Frank Staals, Lorenzo Theunissen

Proc. 42th Annual Symposium on Computational Geometry, 2026

To Appear

Download Local Copy View Slides Export Citation

@inproceedings{dynApproxNNPolygonalDomain2026,
  author = {van der Laan, Joost and Staals, Frank and Theunissen, Lorenzo},
  title = {Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain},
  booktitle = {Proc. 42th Annual Symposium on Computational Geometry},
  year = {2026},
  location = {New Brunswick, NJ, USA},
  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},
  note = {To Appear},
}

On Strictly Output-Sensitive Color Frequency Reporting

Erwin Glazenburg, Frank Staals

SOFSEM 2026: Theory and Practice of Computer Science, 2026

Invited for a special in DMTCS on SOFSEM 2026

Download Local Copy View Slides Export Citation

@incollection{type2counting2026,
  author = {Glazenburg, Erwin and Staals, Frank},
  title = {On Strictly Output-Sensitive Color Frequency Reporting},
  booktitle = {{SOFSEM} 2026: Theory and Practice of Computer Science},
  series = {LNCS},
  year = {2026},
  location = {Krak{\'{o}}w, Poland},
  publisher = {Springer},
  category = {datastructures},
  pages = {246--259},
  doi = {10.1007/978-3-032-17801-5_18},
  url = {https://doi.org/10.1007/978-3-032-17801-5_18},
  note = {Invited for a special in DMTCS on SOFSEM 2026},
}

Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter

Gianmarco Picaralla, Marc van Kreveld, Frank Staals, Sjoerd de Vries

Proc. 30th European Symposium on Algorithms, 2025

Download Local Copy View Slides Export Citation

@inproceedings{maxconvexDiam2025,
  author = {Picaralla, Gianmarco and van Kreveld, Marc and Staals, Frank and de Vries, Sjoerd},
  title = {Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter},
  booktitle = {Proc. 30th European Symposium on Algorithms},
  year = {2025},
  location = {Warsaw, Pland},
  keywords = {convex polygon, dynamic programming, implementation},
  category = {other},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.ESA.2025.23},
  url = {https://doi.org/10.4230/LIPIcs.ESA.2025.23},
}

Nearest Neighbor Searching in a Dynamic Simple Polygon

Sarita de Berg, Frank Staals

Proc. 41th Annual Symposium on Computational Geometry, 2025

Download Local Copy View Slides Export Citation

@inproceedings{nnDynamicPoly2025,
  author = {de Berg, Sarita and Staals, Frank},
  title = {Nearest Neighbor Searching in a Dynamic Simple Polygon},
  booktitle = {Proc. 41th Annual Symposium on Computational Geometry},
  year = {2025},
  location = {Kanazawa Japan},
  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 = {10.4230/LIPIcs.SoCG.2025.37},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2025.37},
}

Convexity Helps Iterated Search in 3D

Peyman Afshani, Yakov Nekrich, Frank Staals

Proc. 41th Annual Symposium on Computational Geometry, 2025

Invited for a Special Issue on SoCG 2025 in JoCG

Download Local Copy View Slides Export Citation

@inproceedings{convexityHelps3d2025,
  author = {Afshani, Peyman and Nekrich, Yakov and Staals, Frank},
  title = {Convexity Helps Iterated Search in 3D},
  booktitle = {Proc. 41th Annual Symposium on Computational Geometry},
  year = {2025},
  location = {Kanazawa Japan},
  keywords = {data structure, range searching, fractional cascading},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2025.3},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2025.3},
  note = {Invited for a Special Issue on SoCG 2025 in JoCG},
}

Range Counting Oracles for Geometric Problems

Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David Woodruff

Proc. 41th Annual Symposium on Computational Geometry, 2025

Download Local Copy View Slides Export Citation

@inproceedings{sublinearemst2025,
  author = {Driemel, Anne and Monemizadeh, Morteza and Oh, Eunjin and
                 Staals, Frank and Woodruff, David},
  title = {Range Counting Oracles for Geometric Problems},
  booktitle = {Proc. 41th Annual Symposium on Computational Geometry},
  year = {2025},
  location = {Kanazawa Japan},
  keywords = {Range counting oracles, minimum spanning trees, Earth Mover's Distance},
  category = {other},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2025.42},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2025.42},
}

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

Erwin Glazenburg, Marc Kreveld, Frank Staals

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

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 $\mathbb{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},
  doi = {10.4230/LIPIcs.ISAAC.2024.34},
  url = {https://doi.org/10.4230/LIPIcs.ISAAC.2024.34},
  pages = {34:1-34:14},
}

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

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},
  doi = {10.4230/LIPIcs.ISAAC.2024.33},
  url = {https://doi.org/10.4230/LIPIcs.ISAAC.2024.33},
  pages = {33:1-33:14},
}

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

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},
  doi = {10.4230/LIPIcs.ISAAC.2024.25},
  url = {https://doi.org/10.4230/LIPIcs.ISAAC.2024.25},
  pages = {25:1--25:15},
}

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

Invited for a Special Issue on SoCG 2024 in JoCG

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},
  note = {Invited for a Special Issue on SoCG 2024 in JoCG},
}

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

Invited for a Special Issue on SoCG 2023 in JoCG

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},
  note = {Invited for a Special Issue on SoCG 2023 in JoCG},
}

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, 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},
}

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

Sarita de Berg, Till Miltzow, Frank Staals

Transactions on Algorithms, 2026

To appear.

Download Local Copy View Slides Export Citation

@article{twoptsp2026,
  author = {de Berg, Sarita and Miltzow, Till and Staals, Frank},
  title = {Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain},
  journal = {Transactions on Algorithms},
  publisher = {ACM},
  category = {trajectories},
  year = {2026},
  keywords = {data structures, geodesic distance, polygonal domain},
  project = {twoptsp2024},
  note = {To appear.},
}

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

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

Journal of Computational Geometry, 2025

Special issue on SoCG 2024.

Download Local Copy View Slides Export Citation

@article{emdut2025,
  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},
  year = {2025},
  keywords = {emd},
  category = {other},
  journal = {Journal of Computational Geometry},
  note = {Special issue on SoCG 2024.},
  url = {https://doi.org/10.20382/jocg.v16i2a10},
  doi = {10.20382/jocg.v16i2a10},
  volume = {16},
  pages = {1--39},
  number = {2},
  project = {emdut2024},
}

Improved Algorithms for Subtrajectory Clustering and Map Construction

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

Journal of Computational Geometry, 2025

Download Local Copy View Slides Export Citation

@article{mapconstruction2025,
  author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and
                 Hendriks, Jorren and Jacobs, Roel and Hosseini Sereshgi, Erfan
                 and I. Silveira, Rodrigo and Sleijster, Jorrick and Staals, Frank and
                  Wenk, Carola},
  title = {Improved Algorithms for Subtrajectory Clustering and Map Construction},
  journal = {Journal of Computational Geometry},
  keywords = {trajectory, moving entity, geometric algorithms},
  category = {trajectories},
  volume = {196},
  year = {2025},
  numpages = {32},
  doi = {10.1016/j.cageo.2024.105845},
  url = {https://doi.org/10.1016/j.cageo.2024.105845},
}

Shortest Paths in Portalgons

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

Journal of Computational Geometry, 2025

Special issue on SoCG 2023.

Download Local Copy View Slides Export Citation

@article{portalgons2025,
  author = {L{\"o}ffler, Maarten and Ophelders, Tim and
                 I. Silveira, Rodrigo and Staals, Frank},
  title = {Shortest Paths in Portalgons},
  year = {2025},
  keywords = {data structure, nearest neighbor, classification},
  category = {geodesic},
  journal = {Journal of Computational Geometry},
  project = {portalgons2023},
  note = {Special issue on SoCG 2023.},
  url = {https://doi.org/10.20382/jocg.v15i2a6},
  doi = {10.20382/jocg.v15i2a6},
  volume = {15},
  pages = {1--48},
  number = {2},
}

Chromatic \(k\)-Nearest Neighbor Queries

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

Journal of Computational Geometry, 2025

Download Local Copy View Slides Export Citation

@article{chromatic_knn2025,
  author = {van der Horst, Thijs and L{\"o}ffler, Maarten and Staals, Frank},
  title = {Chromatic $k$-Nearest Neighbor Queries},
  year = {2025},
  keywords = {data structure, nearest neighbor, classification},
  category = {datastructures},
  journal = {Journal of Computational Geometry},
  project = {chromatic_knn2022},
  doi = {10.20382/jocg.v16i1a3},
  url = {https://doi.org/10.20382/jocg.v16i1a3},
  volume = {16},
  number = {1},
  pages = {1--43},
}

The Complexity of Geodesic Spanners

Sarita de Berg, Marc van Kreveld, Frank Staals

Journal of Computational Geometry, 2024

Download Local Copy View Slides Export Citation

@article{geodesic_spanners2024,
  author = {de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
  title = {The Complexity of Geodesic Spanners},
  journal = {Journal of Computational Geometry},
  year = {2024},
  keywords = {spanner, simple polygon, geodesic distance, complexity},
  category = {geodesic},
  doi = {10.20382/jocg.v15i1a2},
  pages = {1--45},
  url = {https://doi.org/10.20382/jocg.v15i1a2},
  volume = {15},
  project = {geodesic_spanners2023},
}

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.},
}

Strictly output sensitive color frequency reporting

Erwin Glazenburg, Frank Staals

Abstr. 41th European Workshop on Computational Geometry (EuroCG), 2025

Download Local Copy View Slides Export Citation

@article{colorcounting_eurocg,
  author = {Glazenburg, Erwin and Staals, Frank},
  title = {Strictly output sensitive color frequency reporting},
  journal = {Abstr. 41th European Workshop on Computational Geometry (EuroCG)},
  year = {2025},
  location = {Prague, Czech Rebuplic},
  numpages = {6},
  category = {datastructures},
}

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 = {classification},
  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},
  project = {segmentvis2022},
}

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 = {geodesic},
  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 = {datastructures},
  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},
}

Geometric Algorithms for Trajectory Analysis

Frank Staals

Utrecht University, 2015

Download Local Copy View Slides Export Citation

@phdthesis{gafta2015,
  author = {Staals, Frank},
  title = {Geometric Algorithms for Trajectory Analysis},
  institution = {Utrecht University},
  year = {2015},
  isbn = {978-90-393-6349-2},
  category = {trajectories},
  url = {https://dspace.library.uu.nl/handle/1874/313870},
}

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},
}

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},
}

Publications

Conference Proceedings

Visibility Queries in Simple Polygons

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Journal Papers

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

Workshop Abstracts

Strictly output sensitive color frequency reporting

Querying the Hausdorff Distance of a Line Segment

Kinetic All-Pairs Shortest Path in a Simple Polygon

Theses

Technical Reports