Fine-grained complexity theory: conditional lower bounds for computational geometry (Q2117766): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3181333534
@@ Property / OpenAlex ID: W3181333534 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5002674
@@ Property / cites work: Q5002674 / rank @@
+Normal rank
@@ Property / cites work @@
+More Applications of the Polynomial Method to Algorithm Design
+Normal rank
@@ Property / cites work @@
+Computing the Discrete Fréchet Distance in Subquadratic Time
+Normal rank
@@ Property / cites work @@
+COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
+Normal rank
@@ Property / cites work @@
+Tight Hardness Results for Maximum Weight Rectangles
+Normal rank
@@ Property / cites work @@
+Fine-Grained Complexity Theory (Tutorial)
@@ Property / cites work: Fine-Grained Complexity Theory (Tutorial) / rank @@
+Normal rank
@@ Property / cites work @@
+Polyline simplification has cubic complexity
@@ Property / cites work: Polyline simplification has cubic complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
+Normal rank
@@ Property / cites work @@
+Q4607967
@@ Property / cites work: Q4607967 / rank @@
+Normal rank
@@ Property / cites work @@
+Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
+Normal rank
@@ Property / cites work @@
+Approximability of the discrete Fréchet distance
@@ Property / cites work: Approximability of the discrete Fréchet distance / rank @@
+Normal rank
@@ Property / cites work @@
+SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
+Normal rank
@@ Property / cites work @@
+Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
+Normal rank
@@ Property / cites work @@
+An improved approximation algorithm for the discrete Fréchet distance
+Normal rank
@@ Property / cites work @@
+Q5140838
@@ Property / cites work: Q5140838 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the Fréchet distance for realistic curves in near linear time
+Normal rank
@@ Property / cites work @@
+On a class of \(O(n^ 2)\) problems in computational geometry
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
+Normal rank
@@ Property / cites work @@
+Hardness of approximate nearest neighbor search
@@ Property / cites work: Hardness of approximate nearest neighbor search / rank @@
+Normal rank
@@ Property / cites work @@
+ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
+Normal rank
@@ Property / cites work @@
+A new algorithm for optimal 2-constraint satisfaction and its implications
+Normal rank
@@ Property / cites work @@
+Q4607966
@@ Property / cites work: Q4607966 / rank @@
+Normal rank