Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union

Autor: Künnemann, M., Nusser, A.

We revisit the classical problem of determining the largest copy of a simple polygon $P$ that can be placed into a simple polygon $Q$. Despite significant effort, known algorithms require high polynomial running times. (Barequet and Har-Peled, 2001)

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od______1874::883457501393d203fa718553b0f9e845
https://hdl.handle.net/21.11116/0000-0009-B462-D21.11116/0000-0009-B464-B

Finding Small Satisfying Assignments Faster Than Brute Force: {A} Fine-Grained Perspective into {Boolean} Constraint Satisfaction

Autor: Künnemann, M., Marx, D.

Publikováno v: Proceedings of the Computational Complexity Conference 2020
35th Computational Complexity Conference
Leibniz International Proceedings in Informatics

To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean constraint satisfaction with size constraint exactly $k$. More precisely,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f0dd0ace24cc6b7d561d19779c38663

A Fine-Grained Analogue of {S}chaefer's Theorem in {P}: {D}ichotomy of $\exists^k\forall$-Quantified First-Order Graph Properties

Autor: Bringmann, K., Fischer, N., Künnemann, M.

Publikováno v: 34th Computational Complexity Conference
Leibniz International Proceedings in Informatics

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od______1874::7784ebed06fcf124d33f8780a6da8bdf
https://hdl.handle.net/21.11116/0000-0005-1FAF-5

Walking the Dog Fast in Practice: {A}lgorithm Engineering of the {F}r\'{e}chet Distance

Autor: Bringmann, K., Künnemann, M., Nusser, A.

Publikováno v: Journal of Computational Geometry
35th International Symposium on Computational Geometry
Leibniz International Proceedings in Informatics

The Fréchet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in near-quadratic time, a strongly subquadratic algorithm cannot exist unl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::57f4cdba3fb682d3813c228bfcc416ab

Multivariate Fine-Grained Complexity of Longest Common Subsequence

Autor: Bringmann, K., Künnemann, M.

We revisit the classic combinatorial pattern matching problem of finding a longest common subsequence (LCS). For strings $x$ and $y$ of length $n$, a textbook algorithm solves LCS in time $O(n^2)$, but although much effort has been spent, no $O(n^{2-

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od______1874::15f59733769d435169a9a9a3f17f0be1
https://hdl.handle.net/21.11116/0000-0001-3E02-821.11116/0000-0001-3E04-6