Aalto computer scientists in SoCG 2024
The 40th International Symposium on Computational Geometry () is organized in Athens, Greece, June 11鈥14 2024, as part of the Computational Geometry (CG) Week. This year three papers from Aalto University were accepted to the conference.
Accepted papers
In alphabetical order. Click the title to see the authors and the abstract.
Authors
Karl Bringmann, Frank Staals, Karol Wegrzycki and Geert van Wordragen
Abstract
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 point sets. The Earth Mover's Distance under Translation (EMDuT) is a translation-invariant version thereof. It minimizes the Earth Mover's Distance over all translations of one point set. For EMDuT in 鈩1, we present an 顖凰(n2)-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For EMDuT in 鈩漝, we present an 顖凰(n2d+2)-time algorithm for the L1 and L鈭 metric. We show that this dependence on d is asymptotically tight, as an no(d)-time algorithm for L1 or L鈭 would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems.
Authors
S谩ndor Kisfaludi-Bak, Jana Masa艡铆kov谩, Erik Jan van Leeuwen, Bartosz Walczak and Karol W臋grzycki
Abstract
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar 未-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed 未鈮0, we can find balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set Z) with any subset of the connected components of G鈭抁induces again a planar 未-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that size of separator is poly(未)鈰卨ogn. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar 未-hyperbolic graphs. We prove that Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant 未, running in npolylog(n)鈰2顖(未2)鈰呂碘垝顖(未) time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no no(未)-time algorithm on planar 未-hyperbolic graphs, unless ETH fails.
Authors
S谩ndor Kisfaludi-Bak and Geert van Wordragen
Abstract
We propose a data structure in d-dimensional hyperbolic space that can be considered a natural counterpart to quadtrees in Euclidean spaces. Based on this data structure we propose a so-called L-order for hyperbolic point sets, which is an extension of the Z-order defined in Euclidean spaces. Using these quadtrees and the L-order we build geometric spanners. Near-linear size (1+系)-spanners do not exist in hyperbolic spaces, but we are able to create a Steiner spanner that achieves a spanning ratio of 1+系 with 顖籨,系(n) edges, using a simple construction that can be maintained dynamically. As a corollary we also get a (2+系)-spanner (in the classical sense) of the same size, where the spanning ratio 2+系 is almost optimal among spanners of subquadratic size. Finally, we show that our Steiner spanner directly provides a solution to the approximate nearest neighbour problem: given a point set P in d-dimensional hyperbolic space we build the data structure in 顖籨,系(nlogn) time, using 顖籨,系(n) space. Then for any query point q we can find a point p鈭圥 that is at most 1+系 times farther from q than its nearest neighbour in P in 顖籨,系(logn) time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time 顖籨,系(logn).
Related news
Tough questions through computational geometry
S谩ndor Kisfaludi-Bak started as assistant professor at the Department of Computer Science in January. He is looking forward to collaborative research and illuminating the beauty of computational geometry to students and colleagues alike.
Department of Computer Science
We are an internationally-oriented community and home to world-class research in modern computer science.
School of Science
Science for tomorrow鈥檚 technology, innovations and businesses
Read more news
Research Council of Finland establishes a Center of Excellence in Quantum Materials
The Centre, called QMAT, creates new materials to power the quantum technology of coming decades.
Major funding powers development of next-generation machine technology aimed at productivity leap in export sectors
The BEST research project is developing new types of sealing, bearing, and damping technology.
The TAIMI project builds an equal working life 鈥 a six-year consortium project seeks solutions to recruitment and skill challenges
Artificial intelligence (AI) is changing skill requirements, the population is aging, and the labor shortage is deepening. Meanwhile, the potential of international experts often remains unused in Finland. These challenges in working life are addressed by the six-year TAIMI project funded by the Strategic Research Council, and implemented by a broad consortium.