Publications

Conference Proceedings

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
@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

@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, Frank Staals, Valentin Polishchuk

Proc. 2019 WADS Algorithms and Data Structures Symposium, 2019

@incollection{blocking_stick2019,
  author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                 and Polishchuk, Valentin},
  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

@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

@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

@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

@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

@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

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

Computing the Expected Value and the Variance of Geometric Measures

Frank Staals, Constantinos Tsirogiannis

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

Invited for a special issue on ALENEX 2017 in the ACM Journal of Experimental Algorithmics
@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
@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

@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

@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
@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

@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

@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

@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
@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

@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

@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

@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

@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

@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

@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

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

Journal Papers

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. To Appear.
@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. To Appear.},
  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
@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.
@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

@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
@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 = {trajectories},
  year = {2017},
  project = {minlinkpath2016},
  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

@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.
@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

@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

@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

@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.
@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

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

Workshop Abstracts

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

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

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

@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 = {trajectories},
  url = {http://www.eurocg2019.uu.nl/papers/24.pdf},
}

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.
@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

@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

@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

@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

@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

@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

@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

@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

@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

@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

@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

@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

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

Theses

Geographic Grid Embeddings

Frank Staals

Eindhoven University of Technology, 2011

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