2.8k citations
- Max Planck SocietyDE261 papers
- Saarland UniversityDE124 papers
- Technische Universität BerlinDE55 papers
- Centre National de la Recherche ScientifiqueFR41 papers
- Korea UniversityKR41 papers
- Stanford UniversityUS25 papers
- Institut national de recherche en sciences et technologies du numériqueFR24 papers
- ETH ZurichCH21 papers
- Helmholtz Center for Information SecurityDE20 papers
- Technical University of MunichDE20 papers
- Université de LorraineFR17 papers
- University of LuxembourgLU16 papers
29 papers · 1 filter
Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
Mark de Berg, Sándor Kisfaludi-Bak
Recently it was shown that many classic graph problems -- Independent Set, Dominating Set, Hamiltonian Cycle, and more -- can be solved in subexponential time on unit-ball graphs.…
Fine-Grained Complexity of Earth Mover's Distance under Translation
Karl Bringmann, Frank Staals, Karol Węgrzycki +1
The Earth Mover's Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two poin…
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry
Karl Bringmann
Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectu…
Polygon Queries for Convex Hulls of Points
Eunjin Oh, Hee-Kap Ahn
We study the following range searching problem: Preprocess a set of points in the plane with respect to a set of orientations % , for a constant, in the p…
Point Location in Incremental Planar Subdivisions
Eunjin Oh
We study the point location problem in incremental (possibly disconnected) planar subdivisions, that is, dynamic subdivisions allowing insertions of edges and vertices only. Specif…
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann +5
We consider very natural "fence enclosure" problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set of points in th…