• 1290 Citations
20052020

Research output per year

If you made any changes in Pure these will be visible here soon.

Research Output

2020

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency: Proceedings of the 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR 20)

Afshani, P., de Berg, M. T., Buchin, K. A., Gao, J., Löffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H. & Yang, H-T., 2020, 25 p. Cornell university.

Research output: Other contributionAcademic

Designing art galleries (Media Exposition)

van Benthem, T., Buchin, K., Kostitsyna, I. & Slot, S., 1 Jun 2020, 6th International Symposium on Computational Geometry (SoCG). Cabello, S. & Chen, D. Z. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs-SoCG-2020-80. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 164).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access

Dots & polygons (Media Exposition)

Buchin, K., Hagedoorn, M., Kostitsyna, I., van Mulken, M., Rensen, J. & van Schooten, L., 1 Jun 2020, 36th International Symposium on Computational Geometry (SoCG). Cabello, S. & Chen, D. Z. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs-SoCG-2020-79. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 164).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access

Minimum perimeter-sum partitions in the plane

Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M. & Mehrabi, A. D., 1 Mar 2020, In : Discrete and Computational Geometry. 63, 2, p. 483-505 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

On the Hardness of Computing an Average Curve

Struijs, M. A. C., Buchin, K. A. & Driemel, A., 22 Jun 2020, 17th Scandinavian Symposium and Workshops on Algorithm Theory: SWAT 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 162. p. 19:1-19:19 19 p. 19

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access

The angular blowing-a-kiss problem

Struijs, M. A. C., Buchin, K. A., Kostitsyna, I. & Lambers, R., 16 Mar 2020, EuroCG 2020: Book of Abstracts, 36th European Workshop on Computational Geometry. p. 74:1-74:7 7 p. 74

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

2019

Approximating (k,ℓ)-center clustering for curves

Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., Löffler, M. & Struijs, M., 2 Jan 2019, 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Chan, T. M. (ed.). Society for Industrial and Applied Mathematics (SIAM), p. 2922-2938 17 p.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Open Access
3 Citations (Scopus)
1 Downloads (Pure)

A sampling-based strategy for distributing taxis in a road network for occupancy maximization (GIS Cup)

Buchin, K. A., Kostitsyna, I., Custers, B. & Struijs, M. A. C., 5 Nov 2019, 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019. Banaei-Kashani, F., Trajcevski, G., Guting, R. H., Kulik, L. & Newsam, S. (eds.). Association for Computing Machinery, Inc, p. 616-619 4 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

A spanner for the day after

Buchin, K., Har-Peled, S. & Oláh, D., 1 Jun 2019, 35th International Symposium on Computational Geometry, SoCG 2019. Barequet, G. & Wang, Y. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 15 p. 19. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 129).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
7 Downloads (Pure)

Hardness results on voronoi, laguerre and apollonius diagrams

Buchin, K., Castro, P. M. H. M. D., Devillers, O. & Karavelas, M., 10 Aug 2019, Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019. p. 99-104 6 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Klcluster: center-based clustering of trajectories

Buchin, K. A., Driemel, A., van de L'Isle, N. A. F. & Nusser, A., 5 Nov 2019, 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2019. Banaei-Kashani, F., Trajcevski, G., Guting, R. H., Kulik, L. & Newsam, S. (eds.). New York: Association for Computing Machinery, Inc, p. 496-499 4 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Locally correct Fréchet matchings

Buchin, K., Buchin, M., Meulemans, W. & Speckmann, B., 1 Jan 2019, In : Computational Geometry. 76, p. 1-18 18 p.

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

On the hardness of computing an average curve

Buchin, K. A., Driemel, A. & Struijs, M. A. C., 21 Feb 2019, In : arXiv. 15 p., 1902.08053v1.

Research output: Contribution to journalArticleAcademic

Open Access
File
5 Downloads (Pure)

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Buchin, K., Kostitsyna, I., Löffler, M. & Silveira, R. I., 1 Jul 2019, In : Algorithmica. 81, 7, p. 2682–2715 34 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
30 Downloads (Pure)

Seth says: weak Fréchet distance is faster, but only if it is continuous and in one dimension

Buchin, K., Ophelders, T. & Speckmann, B., 1 Jan 2019, SODA '19 Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: Association for Computing Machinery, Inc, p. 2887-2899 13 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)

Visual exploration of migration patterns in gull data

Konzack, M., Gijsbers, P., Timmers, F., van Loon, E., Westenberg, M. A. & Buchin, K., 1 Jan 2019, In : Information Visualization. 18, 1, p. 138-152 15 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
2 Citations (Scopus)
20 Downloads (Pure)
2018

{O}(k)-robust spanners in one dimension

Buchin, K. A., Hulshof, W. J. T. T. & Olah, D., 2018, 6 p. Cornell university.

Research output: Other contributionAcademic

Open Access
File
3 Downloads (Pure)

Approximating $(k,\ell)$-center clustering for curves

Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., Löffler, M. & Struijs, M., 3 May 2018, In : arXiv. 24 p., 1805.01547v2.

Research output: Contribution to journalArticleAcademic

Open Access
File
10 Downloads (Pure)

Approximating the distribution of the median and other robust estimators on uncertain data

Buchin, K. A., Phillips, J. M. & Tang, P., 1 Jun 2018, 34th International Symposium on Computational Geometry, SoCG 2018. Toth, C. D. & Speckmann, B. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14 p. 16. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 99).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Open Access
File
4 Downloads (Pure)

A spanner for the day after

Buchin, K. A., Har-Peled, S. & Olah, D., 2018, 21 p. Cornell university.

Research output: Other contributionAcademic

Open Access
File
4 Downloads (Pure)

Computing the similarity between moving curves

Buchin, K., Ophelders, T. & Speckmann, B., Aug 2018, In : Computational Geometry. 73, p. 2-14 13 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
49 Downloads (Pure)

Model-based segmentation and classification of trajectories

Alewijnse, S. P. A., Buchin, K., Buchin, M., Sijben, S. & Westenberg, M. A., 1 Aug 2018, In : Algorithmica. 80, 8, p. 2422-2452 31 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
3 Citations (Scopus)
29 Downloads (Pure)

Placing your coins on a shelf

Alt, H., Buchin, K. A., Chaplick, S., Cheong, O., Kindermann, P., Knauer, C. & Stehn, F., 2018, In : Journal of Computational Geometry. 9, 1, p. 312-327

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
7 Downloads (Pure)

Progressive simplification of polygonal curves

Buchin, K. A., Konzack, M. P. & Reddingius, W. W. T., 2018, In : arXiv. 20 p., 1806.02647v1.

Research output: Contribution to journalArticleAcademic

Open Access
File
13 Downloads (Pure)
2017

Compact flow diagrams for state sequences

Buchin, K., Buchin, M., Gudmundsson, J., Horton, M. & Sijben, S., 1 Dec 2017, In : Journal on Experimental Algorithmics. 22, 1, 23 p., a7.

Research output: Contribution to journalArticleAcademicpeer-review

Computing the Fréchet distance between real-valued surfaces

Buchin, K., Ophelders, T. & Speckmann, B., 2017, Proc. 28th Annual Symposium on Discrete Algorithms (SODA). Klein, P. N. (ed.). Philadelphia: Association for Computing Machinery, Inc, p. 2443-2455 13 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
3 Citations (Scopus)
87 Downloads (Pure)

Distribution-sensitive construction of the greedy spanner

Alewijnse, S. P. A., Bouts, Q. W., ten Brink, A. P. & Buchin, K. A., 1 May 2017, In : Algorithmica. 78, 1, p. 209-231 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
1 Citation (Scopus)
77 Downloads (Pure)

Efficient trajectory queries under the Fréchet distance (GIS Cup)

Buchin, K. A., Diez, Y., van Diggelen, T. W. T. & Meulemans, W., 7 Nov 2017, Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS). Ravada, S., Hoel, E., Tamassia, R., Newsam, S., Trajcevski, G. & Trajcevski, G. (eds.). New York: Association for Computing Machinery, Inc, 5 p. 101

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
5 Citations (Scopus)
110 Downloads (Pure)

Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves

Buchin, K. A., Chun, J., Markovic, A., Meulemans, W., Löffler, M., Okamoto, Y. & Shiitada, T., 2017, 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia. Katz, M. J. & Aronov, B. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 641-645 5 p. 64. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 77).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
2 Citations (Scopus)
37 Downloads (Pure)

Four Soviets walk the dog: improved bounds for computing the Fréchet distance

Buchin, K. A., Buchin, M., Meulemans, W. & Mulzer, W., 1 Jul 2017, In : Discrete and Computational Geometry. 58, 1, p. 180-216 37 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
11 Citations (Scopus)
85 Downloads (Pure)

Fréchet isotopies to monotone curves

Buchin, K. A., Chambers, E. W., Ophelders, T. A. E. & Speckmann, B., 5 Apr 2017, p. 41-44. 4 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File
24 Downloads (Pure)

Minimum perimeter-sum partitions in the plane

Abrahamsen, M., de Berg, M. T., Buchin, K. A., Mehr, M. & Mehrabi, A. D., 1 Jun 2017, 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia . Katz, M. J. & Aronov, B. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-15 15 p. 4. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 77).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Minimum perimeter-sum partitions in the plane

Abrahamsen, M., de Berg, M. T., Buchin, K. A., Mehr, M. & Mehrabi, A. D., 2017, In : arXiv. 1703.05549, 19 p., 1703.05549.

Research output: Contribution to journalArticleAcademic

Open Access
File
48 Downloads (Pure)

Placing your coins on a shelf

Alt, H., Buchin, K. A., Chaplick, S., Cheong, O., Kindermann, P., Knauer, C. & Stehn, F., 1 Dec 2017, In : arXiv. 1707.01239, 12 p., 1707.01239.

Research output: Contribution to journalArticleAcademic

Open Access
File
20 Downloads (Pure)

Range-clustering queries

Abrahamsen, M., de Berg, M. T., Buchin, K. A., Mehr, M. & Mehrabi, A. D., 2017, 33rd International Symposium on Computational Geometry (SoCG 2017), 14-17 July 2017, Brisbane, Australia. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-16 16 p. 5. (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

Range-clustering queries

Abrahamsen, M., de Berg, M. T., Buchin, K. A., Mehr, M. & Mehrabi, A. D., 2017, In : arXiv. 1705.06242, 23 p., 1705.06242.

Research output: Contribution to journalArticleAcademic

Open Access
File
17 Downloads (Pure)

Ruler of the plane - Games of geometry

Beekhuis, S., Buchin, K., Castermans, T., Hurks, T. & Sonke, W., 1 Jun 2017, 33rd International Symposium on Computational Geometry (SoCG). Aronov, B. & Katz, M. J. (eds.). Leibnitz: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 631-635 5 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 77).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
2 Citations (Scopus)
62 Downloads (Pure)

Visual analytics of delays and interaction in movement data

Konzack, M. P., McKetterick, T., Ophelders, T. A. E., Buchin, M. E., Giuggioli, L., Long, J., Nelson, T., Westenberg, M. A. & Buchin, K. A., 1 Feb 2017, In : International Journal of Geographical Information Science. 31, 2, p. 320-345 26 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
13 Citations (Scopus)
2 Downloads (Pure)
2016

Adjacency-preserving spatial treemaps

Buchin, K. A., Eppstein, D., Löffler, M., Nöllenburg, M. & Silveira, R., 2016, In : Journal of Computational Geometry. 7, 1, p. 100-122 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
69 Downloads (Pure)

Area-preserving simplification and schematization of polygonal subdivisions

Buchin, K., Meulemans, W., Van Renssen, A. & Speckmann, B., 8 Apr 2016, In : ACM Transactions on Spatial Algorithms and Systems . 2, 1, p. 1-36 36 p., 2.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
6 Citations (Scopus)
150 Downloads (Pure)

Compact flow diagrams for state sequences

Buchin, K. A., Buchin, M. E., Gudmundsson, J., Horton, M. J. & Sijben, S., 2016, Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings. Cham: Springer, p. 89-104 (Lecture Notes in Computer Science; vol. 9685).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Compact flow diagrams for state sequences

Buchin, K. A., Buchin, M. E., Gudmundsson, J., Horton, M. J. & Sijben, S., 17 Feb 2016, In : arXiv. 1602.05622 , 18 p.

Research output: Contribution to journalArticleAcademic

Open Access
File
3 Citations (Scopus)
58 Downloads (Pure)

Computing the Fréchet distance between real-valued surfaces

Buchin, K. A., Ophelders, T. A. E. & Speckmann, B., 2016, p. 239-242. 4 p.

Research output: Contribution to conferenceAbstractAcademic

Open Access
File
81 Downloads (Pure)

Computing the Fréchet distance with a retractable leash

Buchin, K. A., Buchin, M. E., van Leusden, R., Meulemans, W. & Mulzer, W., 22 Jun 2016, In : Discrete and Computational Geometry. 56, 2, p. 315-336

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
6 Citations (Scopus)
79 Downloads (Pure)

Fine-grained complexity analysis of two classic TSP variants

de Berg, M. T., Buchin, K. A., Jansen, B. M. P. & Woeginger, G. J., 10 Jul 2016, In : arXiv. 1607.02725v1, 30 p.

Research output: Contribution to journalArticleAcademic

Open Access
File
14 Citations (Scopus)
44 Downloads (Pure)

Fine-grained complexity analysis of two classic TSP variants

de Berg, M. T., Buchin, K. A., Jansen, B. M. P. & Woeginger, G. J., 2016, 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), 11-15 July 2016, Rome, Italy. p. 1-14 5

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

14 Citations (Scopus)
3 Downloads (Pure)

Geo word clouds

Buchin, K. A., Creemers, D. J. A., Lazzarotto, A., Speckmann, B. & Wulms, J. J. H. M., 2016, 2016 IEEE Pacific Visualization Symposium (PacificVis), 19-22 April 2016, Taipei, Taiwan . Piscataway: Institute of Electrical and Electronics Engineers, p. 144-151

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Open Access
File
11 Citations (Scopus)
175 Downloads (Pure)
2015

Analysis and visualisation of movement: an interdisciplinary review

Demšar, U., Buchin, K. A., Cagnacci, F., Safi, K., Speckmann, B., de Weghe, N., Weiskopf, D. & Weibel, R., 2015, In : Movement Ecology. 3, 5, 24 p., 5.

Research output: Contribution to journalReview articleAcademicpeer-review

Open Access
File
75 Citations (Scopus)
91 Downloads (Pure)

Analyzing delays in trajectories

Konzack, M. P., McKetterick, T., Wilcox, G., Buchin, M., Giuggioli, L., Gudmundsson, J., Westenberg, M. A. & Buchin, K., 2015, 2015 IEEE Pacific Visualization Symposium (PacificVis, Hangzhou, China, April 14-17, 2015). Piscataway: Institute of Electrical and Electronics Engineers, p. 93-97

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

Angle-restricted Steiner arborescences for flow map layout

Buchin, K., Speckmann, B. & Verbeek, K. A. B., 2015, In : Algorithmica. 72, 2, p. 656-685 30 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
8 Citations (Scopus)
176 Downloads (Pure)