Publications

Conference Proceedings

  • 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
    To Appear. 
    @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 L. Vermeulen, Jordi 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},
  note = {To Appear.},
}

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

  • 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://dx.doi.org/10.1137/1.9781611974768.19},
  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

  • 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

  • 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

  • Geometric Algorithms for Trajectory Analysis

    Frank Staals

    Utrecht University, 2015 
    @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 = {http://dspace.library.uu.nl/handle/1874/313870},
}

  • 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 = {http://alexandria.tue.nl/extra1/afstversl/wsk-i/staals2011.pdf},
  urldate = {2012-02-05},
  supervisor = {Speckmann, Bettina},
  category = {visualization},
  project = {gridmaps2013},
}