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

To Appear.

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},
  location = {Larnaca, Cyprus},
  publisher = {Springer},
  category = {trajectories},
  note = {To Appear.},
}

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 (virtual conference)},
  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 Hoog van der, 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 Hoog van der, 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},
  category = {datastructures},
  url = {https://doi.org/10.4230/LIPIcs.SWAT.2020.23},
  doi = {10.4230/LIPIcs.SWAT.2020.23},
  pages = {23:1--23:22},
  volume = {162},
}

Maximum Physically Consistent Trajectories

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

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

Won Best Paper at SIGSPATIAL ’19

Download Local Copy View Slides Export Citation

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

An Experimental Evaluation of Grouping Definitions for Moving Entities

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

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

Download Local Copy View Slides Export Citation

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

Most vital segment barriers

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

Proc. 2019 WADS Algorithms and Data Structures Symposium, 2019

Download Local Copy View Slides Export Citation

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

Convex Partial Transversals of Planar Regions

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

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

Download Local Copy View Slides Export Citation

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

An experimental comparison of two definitions for groups of moving entities

Lionov Wiratma, Maarten Löffler, Frank Staals

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

Download Local Copy View Slides Export Citation

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

Convexity-Increasing Morphs of Planar Graphs

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

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

Download Local Copy View Slides Export Citation

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

Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polgyon

Pankaj K. Agarwal, Lars Arge, Frank Staals

Proc. 34th Annual Symposium on Computational Geometry, 2018

Download Local Copy View Slides Export Citation

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

Agglomerative Clustering of Growing Squares

Thom Castermans, Bettina Speckmann, Frank Staals, Kevin Verbeek

Proc. 2018 Latin American Theoretical Informatics Symposium, 2018

Download Local Copy View Slides Export Citation

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

Clustering Trajectories for Map Construction

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

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

Download Local Copy View Slides Export Citation

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

Computing the Expected Value and the Variance of Geometric Measures

Frank Staals, Constantinos Tsirogiannis

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

Invited for a special issue on ALENEX 2017 in the ACM Journal of Experimental Algorithmics

Download Local Copy View Slides Export Citation

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

A Refined Definition for Groups of Moving Entities and its Computation

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

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

Invited for a special issue on ISAAC 2016 in the International Journal on Computational Geometry and its Applications

Download Local Copy View Slides Export Citation

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

Homotopy Measures for Representative Trajectories

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

Proc. 24th European Symposium on Algorithms, 2016

Download Local Copy View Slides Export Citation

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

Grouping Time-varying Data for Interactive Exploration

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

Proc. 32th Annual Symposium on Computational Geometry, 2016

Download Local Copy View Slides Export Citation

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

On the complexity of minimum-link path problems

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

Proc. 32th Annual Symposium on Computational Geometry, 2016

Invited for a special issue on SoCG 2016 in the Journal of Computational Geometry

Download Local Copy View Slides Export Citation

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

Trajectory Grouping Structure under Geodesic Distance

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

Proc. 31th Annual Symposium on Computational Geometry, 2015

Download Local Copy View Slides Export Citation

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

Mixed Map Labeling

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

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

Download Local Copy View Slides Export Citation

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

Practical Approaches to Partially Guarding a Polyhedral Terrain

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

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

Download Local Copy View Slides Export Citation

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

Terrain visibility with multiple viewpoints

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

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

Invited for a special issue on ISAAC 2013 in the International Journal on Computational Geometry and its Applications

Download Local Copy View Slides Export Citation

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

Algorithms for Hotspot Computation on Trajectory Data

Joachim Gudmundsson, Marc van Kreveld, Frank Staals

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

Download Local Copy View Slides Export Citation

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

Trajectory Grouping Structure

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

Proc. 2013 WADS Algorithms and Data Structures Symposium, 2013

Download Local Copy View Slides Export Citation

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

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

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

Proc. 29th Annual Symposium on Computational Geometry, 2013

Download Local Copy View Slides Export Citation

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

Improved Grid Map Layout by Point Set Matching

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

IEEE PacificVis, 2013

Download Local Copy View Slides Export Citation

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

Segmentation of Trajectories on Non-Monotone Criteria

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

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

Download Local Copy View Slides Export Citation

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

Cinderella versus the Wicked Stepmother

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

Theoretical Computer Science, 2012

Download Local Copy View Slides Export Citation

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

A splitting line model for directional relations

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

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

Download Local Copy View Slides Export Citation

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

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 = {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

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

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},
  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},
  numpages = {7},
  category = {trajectories},
  url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_65.pdf},
}

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},
  numpages = {8},
  category = {trajectories},
  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},
}

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 = {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.

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

Publications

Conference Proceedings

Journal Papers

On the complexity of minimum-link path problems

Workshop Abstracts

Improved space bounds for Fréchet distance queries

Covering a set of line segments with a few squares

Maximum Physically Consistent Trajectories

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

Kinetic All-Pairs Shortest Path in a Simple Polygon

Theses