Prof. Dr. Maike Buchin

Theoretical Computer Science / Algorithmics

PROFESSOR / HEAD OF CHAIR

Address:
Ruhr-University Bochum
Faculty of Computer Science
Theoretical Computer Science / Algorithmics
Universitätsstr. 150
–D-44801 Bochum

Room:
MC 5.122

Telephone:
+49(0)234 32 23210


Office Hours:
By arrangement


E-Mail:
maike.buchin(at)rub.de

Curriculum Vitae

since 2019 Professor at Ruhr University Bochum
2017-2019 Visiting Professor at Technical University Dortmund
2013-2017 Juniorprofessor at Ruhr University Bochum
2011-2013 Assistant Professor at TU Eindhoven
2010-2011 Researcher at TU Eindhoven
2007-2010 Researcher at Utrecht University
2007 Doctor’s degree in Computer Science (Free University Berlin)
2003 Diploma (roughly equivalent to Masters) in Mathematics (University of Münster)

Courses

Publications

2022

[1] M. Buchin und D. Rohde, „Coresets for (k,ℓ) -median clustering under the Fréchet distance“, in Algorithms and discrete applied mathematics, Puducherry, India, Jan. 2022, Bd. 13179, S. 167–180. doi: 10.1007/978-3-030-95018-7_14.
 
[2] D. Rohde, M. Buchin, A. Driemel, und C. Sohler, „k-Median clustering of spatial data sequences “, Universitätsbibliothek, Ruhr-Universität Bochum, Bochum, 2022. doi: 10.13154/294-9246.
 
[3] L. Selbach, M. Buchin, A. Mosig, und A. Schönhuth, „Constrained decomposition algorithms: Analysis and application in tissue microdissection“, Universitätsbibliothek, Ruhr-Universität Bochum, Bochum, 2022. doi: 10.13154/294-9686.

2021

[1] M. Buchin, A. Driemel, und D. Rohde, „Approximating (k, ℓ)-Median clustering for polygonal curves“, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), San Diego, Jan. 2021, S. 2697–2717. doi: 10.1137/1.9781611976465.160.
 
[2] L. Ryvkin, M. Buchin, und Carola Wenk, „On distance measures for polygonal curves bridging between Hausdorff and Fréchet distance“, Universitätsbibliothek, Ruhr-Universität Bochum, Bochum, 2021. doi: 10.13154/294-8275.
 
[3] L. Selbach, T. Kowalski, K. Gerwert, M. Buchin, und A. Mosig, „Shape decomposition algorithms for laser capture microdissection“, Algorithms for molecular biology, Bd. 16, Nr. 1, Art. Nr. 15, Juli 2021, doi: 10.1186/s13015-021-00193-6.

2020

[1] M. Buchin, A. Driemel, und D. Rohde, „Approximating (k,ℓ)-median clustering for polygonal curves“, 3. September 2020.
 
[2] B. H. Kilgus, M. Buchin, und R. I. Silveira, „Algorithms for representing and comparing the movement of groups: applications and extensions of the Fréchet distance“, Universitätsbibliothek, Ruhr-Universität Bochum, Bochum, 2020.
 
[3] C. Ries, H. U. Simon, und M. Buchin, „Preference-based teaching of geometrical concept classes and a toolbox for the design of minimum disagreement algorithms“, Universitätsbibliothek, Ruhr-Universität Bochum, Bochum, 2020.

2018

[1] M. Buchin, B. H. Kilgus, und A. Kölzsch, „Group diagrams for representing trajectories“, in Proceedings of the 11th ACM SIGSPATIAL International Workshop on Computational Transportation Science, Seattle, 2018, S. 1–10. doi: 10.1145/3283207.3283208.
 
[2] S. P. A. Alewijnse, K. Buchin, M. Buchin, S. Sijben, und M. A. Westenberg, „Model-based segmentation and classification of trajectories“, Algorithmica, Bd. 80, Nr. 8, S. 2422–2452, 2018, doi: 10.1007/s00453-017-0329-x.
 
[3] K. Buchin, M. Buchin, W. Meulemans, und B. Speckmann, „Locally correct Fréchet matchings“, Computational geometry, Bd. 76, S. 1–18, 2018, doi: 10.1016/j.comgeo.2018.09.002.

2017

[1] K. Buchin, M. Buchin, J. Gudmundsson, M. Horton, und S. Sijben, „Compact flow diagrams for state sequences“, Journal of experimental algorithmics, Bd. 22, Nr. 1, S. 1–23, Dez. 2017, doi: 10.1145/3150525.
 
[2] K. Buchin, M. Buchin, W. Meulemans, und W. Mulzer, „Four Soviets walk the dog: improved bounds for computing the Fréchet distance“, Discrete & computational geometry, Bd. 58, Nr. 1, S. 180–216, Juli 2017, doi: 10.1007/s00454-017-9878-7.
 
[3] M. Buchin, „Geometrische Analyse von Trajektorien“, 29. Juni 2017, Publiziert.
[4]
M. Konzack u. a., „Visual analytics of delays and interaction in movement data“, International journal of geographical information science, Bd. 31, Nr. 2, S. 320–345, Feb. 2017, doi: 10.1080/13658816.2016.1199806.
 
[5] S. Sijben, M. Buchin, und W. Mulzer, „Algorithms for comparing and summarising movement data“, Universitätsbibliothek, Ruhr-Universität Bochum, Bochum, 2017.
 
[6] K. Buchin u. a., „Clustering trajectories for map construction“, in SIGSPATIAL’17, Redondo Beach, Calif., 2017, S. A4. doi: 10.1145/3139958.3139964.
[7]
M. Buchin, „Klassifizierung von Trajektorien: Invited Talk“, 2017. [OnlineRessource]. Verfügbar unter: https://www.informatik.uni-konstanz.de/fachbereich/termine/termine-detailansicht/event/27092-Invited-Talk-Klassifizie/tx_cal_phpicalendar/

2016

[1] K. Buchin, M. Buchin, R. van Leusden, W. Meulemans, und W. Mulzer, „Computing the Fréchet distance with a retractable leash“, Discrete & computational geometry, Bd. 56, Nr. 2, S. 315–336, Sep. 2016, doi: 10.1007/s00454-016-9800-8.
 
[2] M. Buchin und C. Thäle, „Feuer, Wasser, Erde, Luft: wir entdecken Platonische Körper“, gehalten auf der Girls’ Day / Boys’ Day, Bochum, 27. April 2016, Publiziert.
 
[3] K. Buchin, M. Buchin, J. Gudmundsson, M. Horton, und S. Sijben, „Compact flow diagrams for state sequences“, Feb. 2016. [OnlineRessource]. Verfügbar unter: https://arxiv.org/abs/1602.05622
 
[4] L. Etienne, T. Devogele, M. Buchin, und G. McArdle, „Trajectory Box Plot: a new pattern to summarize movements“, International journal of geographical information science, Bd. 30, Nr. 5, S. 835–853, 2016, doi: 10.1080/13658816.2015.1081205.
 
[5] K. Buchin, M. Buchin, J. Gudmundsson, M. Horton, und S. Sijben, „Compact flow diagrams for state sequences“, in Experimental algorithms, Sankt Petersburg, 2016, Bd. 9685, S. 89–104. doi: 10.1007/978-3-319-38851-9_7.
 
[6] H.-K. Ahn, H. Alt, M. Buchin, E. Oh, L. Scharf, und C. Wenk, „A middle curve based on discrete Fréchet distance“, in LATIN 2016: theoretical informatics, Ensenada (Mexiko), 2016, First edition., Bd. 9644, S. 14–26. doi: 10.1007/978-3-662-49529-2_2.
 
[7] S. Dodge, R. Weibel, S. C. Ahearn, M. Buchin, und J. A. Miller, „Analysis of movement data“, in International journal of geographical information science, Bd. 30, Nr. 5, London: Taylor & Francis, 2016, S. 825–834. doi: 10.1080/13658816.2015.1132424.

2015

[1] K. Buchin, M. Buchin, M. V. Kreveld, B. Speckmann, und F. Staals, „Trajectory grouping structure“, Journal of computational geometry, Bd. 6, Nr. 1, S. 75–98, 2015, doi: 10.20382/jocg.v6i1a3.
 
[2] M. Konzack u. a., „Analyzing delays in trajectories“, in 2015 IEEE Pacific Visualization Symposium (PacificVis), Hangzhou, 2015, S. 93–97. doi: 10.1109/pacificvis.2015.7156362.
 
[3] M. Buchin und S. Sijben, „Model-based classification of trajectories“, in Algorithms and computation, Nagoya, 2015, Bd. 9472, S. 393–403. doi: 10.1007/978-3-662-48971-0_34.

2014

[1] T. Asano u. a., „Reprint of: Memory-constrained algorithms for simple polygons“, Computational geometry, Bd. 47, Nr. 3B, S. 469–479, 2014, doi: 10.1016/j.comgeo.2013.11.004.
 
[2] R. S. Purves, P. Laube, M. Buchin, und B. Speckmann, „Moving beyond the point: an agenda for research in movement analysis with real data“, in Computers, environment and urban systems, Bd. 47, Nr. SI, New York: Pergamon Press, 2014, S. 1–4. doi: 10.1016/j.compenvurbsys.2014.06.003.
 
[3] K. Buchin, M. Buchin, M. van Kreveld, B. Speckmann, und F. Staals, „Trajectory grouping structure: the video“, in Proceedings of the Thirtieth Annual Symposium on Computational Geometry, Kyoto, 2014, S. 88. doi: 10.1145/2582112.2595646.
 
[4] K. Buchin, M. Buchin, W. Meulemans, und W. Mulzer, „Four Soviets walk the dog: with an application to Alt’s conjecture“, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, Or., 2014, S. 1399–1413. doi: 10.1137/1.9781611973402.103.
 
[5] S. P. A. Alewijnse, K. Buchin, M. Buchin, A. Kölzsch, H. Kruckenberg, und M. A. Westenberg, „A framework for trajectory segmentation by stable criteria“, in Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Dallas, Tex.; Fort Worth, 2014, S. 351–360. doi: 10.1145/2666310.2666415.
 
[6] M. Buchin, S. Dodge, und B. Speckmann, „Similarity of trajectories taking into account geographic context“, Journal of spatial information science, Bd. 9, Nr. 1, S. 101–124, 2014, doi: 10.5311/josis.2014.9.179.
 
[7] M. Buchin, A. Driemel, und B. Speckmann, „Computing the Fréchet distance with shortcuts is NP-hard“, in Proceedings of the Thirtieth Annual Symposium on Computational Geometry, Kyoto, 2014, S. 367. doi: 10.1145/2582112.2582144.
 
[8] M. Buchin, L. Giuggioli, M. van Kreveld, und G. Theraulaz, „Interaction and collective movement processing: (Dagstuhl Seminar 14132)“, Dagstuhl Reports, Bd. 4, Nr. 3, S. 138–152, 2014, doi: 10.4230/dagrep.4.3.138.

2013

[1] K. Buchin, M. Buchin, M. van Kreveld, B. Speckmann, und F. Staals, „Trajectory grouping structure“, in Algorithms and data structures, London (Ontario), 2013, Bd. 8037, S. 219–230. doi: 10.1007/978-3-642-40104-6_19.
 
[2] T. Asano u. a., „Memory-constrained algorithms for simple polygons“, Computational geometry, Bd. 46, Nr. 8, S. 959–969, 2013, doi: 10.1016/j.comgeo.2013.04.005.
 
[3] K. Buchin, M. Buchin, R. van Leusden, W. Meulemans, und W. Mulzer, „Computing the Fréchet distance with a retractable leash“, in Algorithms – ESA 2013, Sophia Antipolis, 2013, Bd. 8125, S. 241–252. doi: 10.1007/978-3-642-40450-4_21.
 
[4] M. Buchin und R. S. Purves, „Computing similarity of coarse and irregular trajectories using space-time prisms“, in Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Orlando, Fla., 2013, S. 456–459. doi: 10.1145/2525314.2525459.
 
[5] K. Buchin u. a., „Median trajectories“, Algorithmica, Bd. 66, Nr. 3, S. 595–614, 2013, doi: 10.1007/s00453-012-9654-2.
 
[6] K. Buchin, M. Buchin, M. van Kreveld, B. Speckmann, und F. Staals, „Trajectory grouping structures“, 2013. [Online]. Verfügbar unter: http://arxiv.org/abs/1303.6127
 
[7] M. Buchin, A. Driemel, und B. Speckmann, „Computing the Fréchet distance with shortcuts is NP-hard“, 2013. [Online]. Verfügbar unter: http://arxiv.org/abs/1307.2097
 
[8] K. Buchin, M. Buchin, R. van Leusden, W. Meulemans, und W. Mulzer, „Computing the Fréchet distance with a retractable leash“, 2013. [Online]. Verfügbar unter: http://arxiv.org/abs/1306.5527

2012

[1] K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, J. Luo, und R. I. Silveira, „Processing aggregated data: the location of clusters in health data“, Geoinformatica, Bd. 16, Nr. 3, S. 497–521, 2012, doi: 10.1007/s10707-011-0143-6.
 
[2] K. Buchin, M. Buchin, W. Meulemans, und W. Mulzer, „Four Soviets walk the dog: with an application to Alt’s conjecture“, 2012. [Online]. Verfügbar unter: http://arxiv.org/abs/1209.4403
 
[3] K. Buchin u. a., „Drawing (complete) binary tanglegrams“, Algorithmica, Bd. 62, Nr. 1, S. 309–332, 2012, doi: 10.1007/s00453-010-9456-3.
 
[4] K. Buchin, M. Buchin, W. Meulemans, und B. Speckmann, „Locally correct Fréchet matchings“, in Algorithms – ESA 2012, Ljubljana, 2012, Bd. 7501, S. 229–240. doi: 10.1007/978-3-642-33090-2_21.
 
[5] M. Buchin, S. Dodge, und B. Speckmann, „Context-aware similarity of trajectories“, in Geographic information science, Columbus, Ohio, 2012, Bd. 7478, S. 43–56. doi: 10.1007/978-3-642-33024-7_4.
 
[6] K. Buchin und M. Buchin, „Rolling block mazes are PSPACE-complete“, Journal of information processing, Bd. 20, Nr. 3, S. 719–722, 2012, doi: 10.2197/ipsjjip.20.719.
 
[7] K. Buchin, M. Buchin, W. Meulemans, und B. Speckmann, „Locally correct Frechet matchings“, 2012. [Online]. Verfügbar unter: http://arxiv.org/abs/1206.6257
 

2011

[1] K. Buchin, M. Buchin, M. van Kreveld, und J. Luo, „Finding long and similar parts of trajectories“, Computational geometry, Bd. 44, Nr. 9, S. 465–476, 2011, doi: 10.1016/j.comgeo.2011.05.004.
 
[2] B. Aronov u. a., „Connect the dot: computing feed-links for network extension“, Journal of spatial information science, Bd. 3, Nr. 1, S. 3–31, 2011, doi: 10.5311/josis.2011.3.47.
 
[3] M. Buchin, A. Driemel, M. van Kreveld, und V. Sacristán, „Segmenting trajectories: a framework and algorithms using spatiotemporal criteria“, Journal of spatial information science, Bd. 3, Nr. 1, S. 33–63, 2011, doi: 10.5311/josis.2011.3.66.
 
[4] K. Buchin, M. Buchin, J. Gudmundsson, M. Löffler, und J. Luo, „Detecting commuting patterns by clustering subtrajectories“, International journal of computational geometry and applications, Bd. 21, Nr. 3, S. 253–282, 2011, doi: 10.1142/s0218195911003652.
 
[5] T. Asano u. a., „Memory-constrained algorithms for simple polygons“, 2011. [Online]. Verfügbar unter: http://arxiv.org/abs/1112.5904

2010

[1] K. Buchin, M. Buchin, und J. Gudmundsson, „Constrained free space diagrams: a tool for trajectory analysis“, International journal of geographical information science, Bd. 24, Nr. 7, S. 1101–1125, 2010, doi: 10.1080/13658810903569598.
 
[2] S. Bereg, K. Buchin, M. Buchin, M. L. Gavrilova, und B. Zhu, „Voronoi diagram of polygonal chains under the discrete fréchet distance“, International journal of computational geometry and applications, Bd. 20, Nr. 4, S. 471–484, 2010, doi: 10.1142/s0218195910003396.
 
[3] K. Buchin u. a., „Median trajectories“, in Algorithms – ESA 2010, Liverpool, 2010, Bd. 6346/6347, S. 463–474. doi: 10.1007/978-3-642-15775-2_40.
 
[4] K. Buchin, M. Buchin, und A. Schulz, „Fréchet distance of surfaces: some simple hard cases“, in Algorithms – ESA 2010, Liverpool, 2010, Bd. 6346/6347, S. 63–74. doi: 10.1007/978-3-642-15781-3_6.
 
[5] M. de Berg u. a., „Results of the break-out group: aggregation“, in Representation, analysis and visualization of moving objects, Wadern, 2010, Bd. 10491. [Online]. Verfügbar unter: http://drops.dagstuhl.de/opus/volltexte/2011/2987/
 
[6] K. Buchin u. a., „Drawing (complete) binary tanglegrams: hardness, approximation, fixed-parameter tractability“, 2010. [Online]. Verfügbar unter: http://arxiv.org/abs/0806.0920
 
[7] H. Alt und M. Buchin, „Can we compute the similarity between surfaces?“, Discrete & computational geometry, Bd. 43, Nr. 1, S. 78–99, 2010, doi: 10.1007/s00454-009-9152-8.
 
[8] E. van Loon u. a., „Results of the break-out group: Gulls data“, in Representation, analysis and visualization of moving objects, Wadern, 2010, Bd. 10491. [Online]. Verfügbar unter: http://drops.dagstuhl.de/opus/volltexte/2011/2991/
 
[9] M. Buchin, A. Driemel, M. van Kreveld, und V. Sacristán, „An algorithmic framework for segmenting trajectories based on spatio-temporal criteria“, in GIS’10, San Jose, Calif., 2010, S. 202–211. doi: 10.1145/1869790.1869821.
 

2009

[1] K. Buchin, M. Buchin, und J. Gudmundsson, „Detecting single file movement“, in GIS’08, 2009, Publiziert. doi: 10.1145/1463434.1463476.
 
[2] N. Alon u. a., „Polychromatic colorings of plane graphs“, Discrete & computational geometry, Bd. 42, Nr. 3, S. 421–442, 2009, doi: 10.1007/s00454-009-9171-5.
 
[3] B. Aronov u. a., „Feed-links for network extensions“, in GIS’08, 2009, Publiziert. doi: 10.1145/1463434.1463478.
 
[4] B. Aronov u. a., „Connect the dot: computing feed-links with minimum dilation“, in Algorithms and data structures, 2009, Bd. 5664, S. 49–60. doi: 10.1007/978-3-642-03367-4_5.
 
[5] K. Buchin, M. Buchin, M. van Kreveld, und J. Luo, „Finding long and similar parts of trajectories“, in Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2009, S. 296–305. doi: 10.1145/1653771.1653813.
 
[6] K. Buchin u. a., „Drawing (complete) binary tanglegrams“, in Graph Drawing, 2009, Bd. 5417, S. 324–335. doi: 10.1007/978-3-642-00219-9_32.
 
[7] K. Buchin, M. Buchin, und Y. Wang, „Exact algorithms for partial curve matching via the Fréchet distance“, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, NY, 2009, S. 645–654. [Online]. Verfügbar unter: http://dl.acm.org/citation.cfm?id=1496770.1496841
 
[8] K. Buchin u. a., „Drawing (Complete) binary tanglegrams : hardness, approximation, fixed-parameter tractability“, in Graph Drawing, 2009, Bd. 5417, S. 324–335. doi: 10.1007/978-3-642-00219-9_32.

2008

[1] K. Buchin, M. Buchin, und C. Wenk, „Computing the Fréchet distance between simple polygons“, Computational geometry, Bd. 41, Nr. 1–2, S. 2–20, 2008, doi: 10.1016/j.comgeo.2007.08.003.
 
[2] K. Buchin, M. Buchin, J. Gudmundsson, M. Löffler, und J. Luo, „Detecting commuting patterns by clustering subtrajectories“, in Algorithms and computation, 2008, Bd. 5369, S. 644–655. doi: 10.1007/978-3-540-92182-0_57.
 
[3] S. Bereg, K. Buchin, M. Buchin, M. L. Gavrilova, und B. Zhu, „Voronoi diagram of polygonal chains under the discrete Fréchet distance“, in Computing and combinatorics, 2008, Bd. 5092, S. 352–362. doi: 10.1007/978-3-540-69733-6_35.
 
[4] N. Alon u. a., „Polychromatic colorings of plane graphs“, in Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry (SCG ’08), 2008, S. 338–345. doi: 10.1145/1377676.1377734.
 
[5] K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, J. Luo, und R. I. Silveira, „Clusters in aggregated health data“, in Headway in spatial data handling, 2008, S. 77–90. doi: 10.1007/978-3-540-68566-1_5.

2007

[1] M. Buchin u. a., „On rolling cube puzzles“, in Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007, S. 141–144.
 
[2] K. Buchin und M. Buchin, „Topology control“, in Algorithms for sensor and ad hoc networks, 2007, Bd. 4621, S. 81–98. doi: 10.1007/978-3-540-74991-2_5.
 
[3] H. Alt und M. Buchin, „Can we compute the similarity between surfaces?“, 2007. [Online]. Verfügbar unter: http://arxiv.org/abs/cs/0703011
 
[4] K. Buchin und M. Buchin, „Lower bounds for the complexity of the Voronoi diagram of polygonal curves under the discrete Frechet distance“, 2007. [Online]. Verfügbar unter: http://arxiv.org/abs/0708.1909

2006

[1] K. Buchin, M. Buchin, und C. Wenk, „Computing the Fréchet distance between simple polygons in polynomial time“, in Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, 2006, S. 80–87. doi: 10.1145/1137856.1137870.
 

2005

[1] M. Buchin und J. Giesen, „Minimizing the total absolute Gaussian curvature in a terrain is hard“, in Proceedings of the 17th Canadian Conference on Computational Geometry, University of Windsor, Ontario, Canada, 2005, S. 195–198. [Online]. Verfügbar unter: http://www.cccg.ca/proceedings/2005/25.pdf
 
[2] H. Alt und M. Buchin, „Semi-computability of the Fréchet distance between surfaces“, in Abstracts for the Twentyfirst European Workshop on Computational Geometry, 2005, S. 45–48. [Online]. Verfügbar unter: http://www.win.tue.nl/EWCG2005/Proceedings/12.pdf

2003

[1] J. Döllner und M. Buchin, „Real-time expressive rendering of city models“, in Proceedings, 2003, S. 245–251. doi: 10.1109/iv.2003.1217986.
 
[2] K. Buchin und M. Buchin, „Real-time per-pixel rendering with stroke textures“, in Proceedings of the 19th Spring Conference on Computer Graphics, Budmerice, Slovakia, 2003, S. 125–129. doi: 10.1145/984952.984974.

Prof. Dr. Maike Buchin

Theoretical Computer Science / Algorithmics

Professor / Head of Chair

Address:
Ruhr-University Bochum
Faculty of Computer Science
Theoretical Computer Science / Algorithmics
Universitätsstr. 150
--D-44801 Bochum

Room: IB 3/145

Telephone: +49(0)234 32 23210

Office Hours: By arrangement

E-Mail: maike.buchin(at)rub.de

Curriculum Vitae

since 2019 Professor at Ruhr University Bochum
2017-2019 Visiting Professor at Technical University Dortmund
2013-2017 Juniorprofessor at Ruhr University Bochum
2011-2013 Assistant Professor at TU Eindhoven
2010-2011 Researcher at TU Eindhoven
2007-2010 Researcher at Utrecht University
2007 Doctor's degree in Computer Science (Free University Berlin)
2003 Diploma (roughly equivalent to Masters) in Mathematics (University of Münster)


Courses



Publications