Intranet English
FAKULTÄT FÜR MATHEMATIK, PHYSIK UND INFORMATIK
Lehrstuhl für Angewandte Informatik VI – Algorithmen und Datenstrukturen

Publikationen

Download BibTeX (.bib)

  1. Better Late than Never: the Complexity of Arrangements of Polyhedra Boris Aronov and Sang Won Bae and Sergio Cabello and Otfried Cheong and David Eppstein and Christian Knauer and Raimund Seidel · 2025 · CoRR, abs/2506.03960
  2. A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains Pankaj K. Agarwal and Boris Aronov and Olivier Devillers and Christian Knauer and Guillaume Moroz · 2025 · 41st International Symposium on Computational Geometry (SoCG 2025), 332, pp. 4:1--4:17
  3. Geometric Matching and Bottleneck Problems Sergio Cabello and Siu-Wing Cheng and Otfried Cheong and Christian Knauer · 2024 · 40th International Symposium on Computational Geometry (SoCG 2024), 293, pp. 31:1--31:15
  4. Parallel near-optimal pathfinding based on landmarks Maximilian Reischl and Christian Knauer and Michael Guthe · 2022 · Computers & Graphics, 102, pp. 1--8
  5. Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU Maximilian Reischl and Christian Knauer and Michael Guthe · 2020 · 28th Pacific Conference on Computer Graphics and Applications (PG 2020), pp. 37--42
  6. Modellbasierte Methode zur Ableitung nicht-funktionaler Anforderungen im Kontext der Softwaremodernisierung Lukas Strey and Christian Hein and Tom Ritter and Christian Knauer and Angelika Ganz · 2020 · Modellierung 2020, P-302, pp. 125--140
  7. Corrigendum to: Approximating minimum-area rectangular and convex containers for packing convex polygons Mark de Berg and Christian Knauer · 2020 · Journal of Computational Geometry, 11, pp. 653--655
  8. The geometric dilation of three points Annette Ebbers-Baumann and Rolf Klein and Christian Knauer and Günter Rote · 2019 · Journal of Computational Geometry (JoCG), 10
  9. On Romeo and Juliet problems: Minimizing distance-to-sight Hee-Kap Ahn and Eunjin Oh and Lena Schlipf and Fabian Stehn and Darren Strash · 2019 · Computational Geometry, 84, pp. 12--21
  10. Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees Große, Ulrike and Knauer, Christian and Stehn, Fabian and Gudmundsson, Joachim and Smid, Michiel · 2019 · International Journal of Foundations of Computer Science, 30, pp. 293-313
  11. Covering Many Points with a Small-Area Box de Berg, Mark and Cabello, Sergio and Cheong, Otfried and Eppstein, David and Knauer, Christian · 2019 · Journal of Computational Geometry (JoCG), 10
  12. The Reverse Kakeya Problem Sang Won Bae and Sergio Cabello and Otfried Cheong and Yoonsung Choi and Fabian Stehn and Sang Duk Yoon · 2018 · 34th International Symposium on Computational Geometry (SoCG 2018), 99, pp. 6:1--6:13
  13. Placing your Coins on a Shelf Helmut Alt and Kevin Buchin and Steven Chaplick and Otfried Cheong and Philipp Kindermann and Christian Knauer and Fabian Stehn · 2018 · Journal of Computational Geometry (JoCG), 9
  14. On Romeo and Juliet Problems: Minimizing Distance-to-Sight Hee-Kap Ahn and Eunjin Oh and Lena Schlipf and Fabian Stehn and Darren Strash · 2018 · 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), 101, pp. 6:1--6:13
  15. Elastic geometric shape matching for translations under the Manhattan norm Christian Knauer and Luise Sommer and Fabian Stehn · 2018 · Computational Geometry, 73, pp. 57 - 69
  16. An FPTAS for an Elastic Shape Matching Problem with Cyclic Neighborhoods Knauer, Christian and Sommer, Luise and Stehn, Fabian · 2018 · Computational Science and Its Applications -- ICCSA 2018, pp. 425--443
  17. Top-k Manhattan spatial skyline queries Wanbin Son and Fabian Stehn and Christian Knauer and Hee-Kap Ahn · 2017 · Inf. Process. Lett., 123, pp. 27--35
  18. Placing your Coins on a Shelf Helmut Alt and Kevin Buchin and Steven Chaplick and Otfried Cheong and Philipp Kindermann and Christian Knauer and Fabian Stehn · 2017 · 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, pp. 4:1--4:12
  19. Minimum Cell Connection in Line Segment Arrangements Alt, Helmut and Cabello, Sergio and Giannopoulos, Panos and Knauer, Christian · 2017 · International Journal of Computational Geometry & Applications, 27, pp. 159-176
  20. Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons Helmut Alt and Mark de Berg and Christian Knauer · 2017 · JoCG, 8, pp. 1--10
  21. Shortest path to a segment and quickest visibility queries Valentin Polishchuk and Esther M. Arkin and Alon Efrat and Christian Knauer and Joseph S. B. Mitchell and Günter Rote and Lena Schlipf and Topi Talvitie and Valentin Polishchuk · 2016 · JoCG, 7, pp. 77--100
  22. Guest Editors' Foreword Christian Knauer and Michiel H. M. Smid · 2016 · Int. J. Comput. Geometry Appl., 26, pp. 0--134
  23. Finding largest rectangles in convex polygons Sergio Cabello and Otfried Cheong and Christian Knauer and Lena Schlipf · 2016 · Comput. Geom., 51, pp. 67-74
  24. Shortest Path to a Segment and Quickest Visibility Queries Esther Arkin and Alon Efrat and Christian Knauer and Joseph Mitchell and Valentin Polishchuk and Günter Rote and Lena Schlipf and Topi Talvitie · 2015 · 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, pp. 658--673
  25. Fixed-Parameter Complexity and Approximability of Norm Maximization Christian Knauer and Stefan König and Daniel Werner · 2015 · Discrete & Computational Geometry, pp. 1-20
  26. Fast Algorithms for Diameter-Optimally Augmenting Paths Ulrike Gro\sse and Joachim Gudmundsson and Christian Knauer and Michiel H. M. Smid and Fabian Stehn · 2015 · Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pp. 678--688
  27. Elastic Geometric Shape Matching for Point Sets under Translations Christian Knauer and Fabian Stehn · 2015 · Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pp. 578--592
  28. Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons Helmut Alt and Mark de Berg and Christian Knauer · 2015 · Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pp. 25--34
  29. Top-k Manhattan Spatial Skyline Queries Wanbin Son and Fabian Stehn and Christian Knauer and Hee-Kap Ahn · 2014 · WALCOM, pp. 22-33
  30. Convex transversals Esther Arkin and Claudia Dieckmann and Christian Knauer and Joseph Mitchell and Valentin Polishchuk and Lena Schlipf and Shang Yang · 2014 · Comput. Geom., 47, pp. 224-239
  31. Realistic roofs over a rectilinear polygon Hee-Kap Ahn and Sang Won Bae and Christian Knauer and Mira Lee and Chan-Su Shin and Antoine Vigneron · 2013 · Comput. Geom., 46, pp. 1042 - 1055
  32. Range-Aggregate Queries for Geometric Extent Problems Peter Brass and Christian Knauer and Chan-Su Shin and Michiel H. M. Smid · 2013 · CATS, pp. 3-10
  33. On the complexity of Erdös-Szekeres and related problems in $\R^3$ Panos Giannopoulos and Christian Knauer and Daniel Werner · 2013 · ESA, pp. 541-552
  34. Fixed-parameter tractability and lower bounds for stabbing problems Panos Giannopoulos and Christian Knauer and Günter Rote and Daniel Werner · 2013 · Comput. Geom., 46, pp. 839--860
  35. Covering and piercing disks with two centers Hee-Kap Ahn and Sang-Sub Kim and Christian Knauer and Lena Schlipf and Chan-Su Shin and Antoine Vigneron · 2013 · Comput. Geom., 46, pp. 253-262
  36. Advantages and Disadvantages of Training based Object Detection / Classification in SAS Images Wolfgang Jans and Christian Knauer and Florian Langner and Wolfgang Middelmann · 2013 · POMA, 17
  37. Largest inscribed rectangles in convex polygons Christian Knauer and Lena Schlipf and Jens M. Schmidt and Hans Raj Tiwary · 2012 · J. Discrete Algorithms, 13, pp. 78-85
  38. Hardness of discrepancy computation and eps-net verification in high dimension Panos Giannopoulos and Christian Knauer and Magnus Wahlström and Daniel Werner · 2012 · J. Complexity, 28, pp. 162-176
  39. Computing the Discrete Frëchet Distance with Imprecise Input Hee-Kap Ahn and Christian Knauer and Marc Scherfenberg and Lena Schlipf and Antoine Vigneron · 2012 · Int. J. Comput. Geometry Appl., 22, pp. 27-44
  40. Approximating the average stretch factor of geometric graphs Siu-Wing Cheng and Christian Knauer and Stefan Langerman and Michiel H. M. Smid · 2012 · JoCG, 3, pp. 132-153
  41. Advantages and Disadvantages of Training based Object Detection / Classification in SAS Images Wolfgang Jans and Christian Knauer and Florian Langner and Wolfgang Middelmann · 2012 · 11th European Conference on Underwater Acoustics, 34, pp. 1629--1636
  42. The directed Hausdorff distance between imprecise point sets Christian Knauer and Maarten Löffler and Marc Scherfenberg and Thomas Wolle · 2011 · Theor. Comput. Sci., 412, pp. 4173-4186
  43. The Aligned k-Center Problem Peter Brass and Christian Knauer and Hyeon-Suk Na and Chan-Su Shin and Antoine Vigneron · 2011 · Int. J. Comput. Geometry Appl., 21, pp. 157-178
  44. On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems Christian Knauer and Hans Raj Tiwary and Daniel Werner · 2011 · STACS, pp. 649-660
  45. On graphs and algebraic graphs that do not contain cycles of length 4 Noga Alon and H. Tracy Hall and Christian Knauer and Rom Pinchasi and Raphael Yuster · 2011 · Journal of Graph Theory, 68, pp. 91-102
  46. Non-uniform Geometric Matchings Christian Knauer and Klaus Kriegel and Fabian Stehn · 2011 · ICCSA (3), pp. 44-57
  47. Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions Christian Knauer and Klaus Kriegel and Fabian Stehn · 2011 · Theor. Comput. Sci., 412, pp. 375-382
  48. Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension Sergio Cabello and Panos Giannopoulos and Christian Knauer and Däniel Marx and Günter Rote · 2011 · ACM Transactions on Algorithms, 7, pp. 43
  49. Generating Realistic Roofs over a Rectilinear Polygon Hee-Kap Ahn and Sang Won Bae and Christian Knauer and Mira Lee and Chan-Su Shin and Antoine Vigneron · 2011 · ISAAC, pp. 60-69
  50. Efficient Dynamical Computation of Principal Components Darko Dimitrov and Mathias Holst and Christian Knauer and Klaus Kriegel · 2011 · GRAPP, pp. 85-93
  51. Covering and Piercing Disks with Two Centers Hee-Kap Ahn and Sang-Sub Kim and Christian Knauer and Lena Schlipf and Chan-Su Shin and Antoine Vigneron · 2011 · ISAAC, pp. 50-59
  52. Convex Transversals Esther Arkin and Claudia Dieckmann and Christian Knauer and Joseph Mitchell and Valentin Polishchuk and Lena Schlipf and Shang Yang · 2011 · WADS, pp. 49-60
  53. Benefit for Screnning by Automated Acoustic Data Fusion Wolfgang Jans and Christian Knauer and Florian Langner and Wolfgang Middelmann · 2011 · Underwater Acoustics Measurements: Technologies and Results, pp. 139-150
  54. Benefit for Classification by Automated Acoustic Data Fusion Alfons Ebert and Wolfgang Jans and Christian Knauer and Florian Langner · 2011 · Underwater Acoustics Measurements: Technologies and Results, pp. 115-122
  55. Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance Christian Knauer and Marc Scherfenberg · 2011 · Int. J. Comput. Geometry Appl., 21, pp. 369-381
  56. A fixed-parameter algorithm for the minimum Manhattan network problem Christian Knauer and Andreas Spillner · 2011 · JoCG, 2, pp. 189-204
  57. The effect of pre-processing on the outcome of an CAD/CAC system for underwater in SAS and conventional side scan images Wolfgang Jans and Christian Knauer and Florian Langner and Wolfgang Middelmann · 2010 · 10th European Conference on Underwater Acoustics, 3, pp. 1262-1270
  58. The Complexity of Geometric Problems in High Dimension Christian Knauer · 2010 · TAMC, pp. 40-49
  59. Performance gain by fusing classification resultes for differenet aspect angles in SAS side scan images Alfons Ebert and Wolfgang Jans and Christian Knauer and Florian Langner · 2010 · 10th European Conference on Underwater Acoustics, 3, pp. 1272-1277
  60. Geometric Hybrid Registration Fabian Stehn · 2010
  61. Dilation-Optimal Edge Deletion in Polygonal Cycles Hee-Kap Ahn and Mohammad Farshi and Christian Knauer and Michiel Smid and Yajun Wang · 2010 · Int. J. Comput. Geometry Appl., 20, pp. 69-87
  62. Covering a simple polygon by monotone directions Hee-Kap Ahn and Peter Brass and Christian Knauer and Hyeon-Suk Na and Chan-Su Shin · 2010 · Comput. Geom., 43, pp. 514-523
  63. Computing the Discrete Frëchet Distance with Imprecise Input Hee-Kap Ahn and Christian Knauer and Marc Scherfenberg and Lena Schlipf and Antoine Vigneron · 2010 · ISAAC (2), pp. 422-433
  64. Computing Geometric Minimum-Dilation Graphs is NP-Hard Panos Giannopoulos and Rolf Klein and Christian Knauer and Martin Kutz and Däniel Marx · 2010 · Int. J. Comput. Geometry Appl., 20, pp. 147-173
  65. Computer Aided Detection and Clasification of MLOs in Side Scan Sonar Images Wolfgang Jans and Christian Knauer and Florian Langner and Wolfgang Middelmann · 2010 · UDT EUROPE 2010, pp. 1-8
  66. Approximating the Average Stretch Factor of Geometric Graphs Siu-Wing Cheng and Christian Knauer and Stefan Langerman and Michiel H. M. Smid · 2010 · ISAAC (1), pp. 37-48
  67. The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension Panos Giannopoulos and Christian Knauer and Günter Rote · 2009 · IWPEC, pp. 198-209
  68. The Directed Hausdorff Distance between Imprecise Point Sets Christian Knauer and Maarten Löffler and Marc Scherfenberg and Thomas Wolle · 2009 · ISAAC, pp. 720-729
  69. Side scan sonar image resolution and automatic object detection, classification and identification Alfons Ebert and Wolfgang Jans and Christian Knauer and Florian Langner · 2009 · OCEANS 2009 - EUROPE, pp. 1-8
  70. On the dilation spectrum of paths, cycles, and trees Rolf Klein and Christian Knauer and Giri Narasimhan and Michiel Smid · 2009 · Comput. Geom., 42, pp. 923-933
  71. On Inducing Polygons and Related Problems Eyal Ackerman and Rom Pinchasi and Ludmila Scharf and Marc Scherfenberg · 2009 · ESA, pp. 47-58
  72. Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions Christian Knauer and Klaus Kriegel and Fabian Stehn · 2009 · FAW, pp. 108-119
  73. Measuring the Similarity of Geometric Graphs Otfried Cheong and Joachim Gudmundsson and Hyo-Sil Kim and Daria Schymura and Fabian Stehn · 2009 · SEA, pp. 101-112
  74. Maximizing the Area of Overlap of Two Unions of Disks under Rigid Motion Sergio Cabello and Mark de Berg and Panos Giannopoulos and Christian Knauer and Renë van Oostrum and Remco C. Veltkamp · 2009 · Int. J. Comput. Geometry Appl., 19, pp. 533-556
  75. Image processing in side scan sonar images for object detection and classification Wolfgang Jans and Christian Knauer and Florian Langner and Wolfgang Middelmann · 2009 · Underwater Acoustic Measurments: Technologies & Results, pp. 311-318
  76. Constructing Optimal Highways Hee-Kap Ahn and Helmut Alt and Tetsuo Asano and Sang Won Bae and Peter Brass and Otfried Cheong and Christian Knauer and Hyeon-Suk Na and Chan-Su Shin and Alexander Wolff · 2009 · Int. J. Found. Comput. Sci., 20, pp. 3-23
  77. Bounds on the quality of the PCA bounding boxes Darko Dimitrov and Christian Knauer and Klaus Kriegel and Günter Rote · 2009 · Comput. Geom., 42, pp. 772-789
  78. Algorithms for graphs of bounded treewidth via orthogonal range searching Sergio Cabello and Christian Knauer · 2009 · Comput. Geom., 42, pp. 815-824
  79. A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem Marc Benkert and Joachim Gudmundsson and Christian Knauer and Renë van Oostrum and Alexander Wolff · 2009 · Int. J. Comput. Geometry Appl., 19, pp. 267-288
  80. Inducing Polygons of Line Arrangements Ludmila Scharf and Marc Scherfenberg · 2008 · ISAAC, pp. 507-519
  81. Approximate Point-to-Surface Registration with a Single Characteristic Point Darko Dimitrov and Christian Knauer and Klaus Kriegel and Fabian Stehn · 2008 · VISAPP (1), pp. 188-195
  82. Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance Christian Knauer and Marc Scherfenberg · 2008 · ISAAC, pp. 532-543
  83. Approximation Algorithms for a Point-to-Surface Registration Problem in Medical Navigation Darko Dimitrov and Christian Knauer and Klaus Kriegel and Fabian Stehn · 2007 · FAW, pp. 26-37