Cover Image

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Park, Seongbin, Oh, Eunjin
Format:	Preprint
Published:	2026
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Exact Algorithms for Clustered Planarity with Linear Saturators
by: Da Lozzo, Giordano, et al.
Published: (2024)

Single-Source Shortest Path Problem in Weighted Disk Graphs
by: An, Shinwoo, et al.
Published: (2025)

Sparse Outerstring Graphs Have Logarithmic Treewidth
by: An, Shinwoo, et al.
Published: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

Fréchet Distance in Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2024)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2025)

Perfect Matchings and Popularity in the Many-to-Many Setting
by: Kavitha, Telikepalli, et al.
Published: (2024)

Range Counting Oracles for Geometric Problems
by: Driemel, Anne, et al.
Published: (2025)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

Touring a Sequence of Orthogonal Polygons
by: Casel, Katrin, et al.
Published: (2026)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Dynamic parameterized problems on unit disk graphs
by: An, Shinwoo, et al.
Published: (2024)

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
by: Depian, Thomas, et al.
Published: (2025)

Ranking and Unranking of the Planar Embeddings of a Planar Graph
by: Di Battista, Giuseppe, et al.
Published: (2024)

Online Algorithms for Geometric Independent Set
by: De, Minati, et al.
Published: (2026)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Algorithms for Computing Closest Points for Segments
by: Wang, Haitao
Published: (2024)

An Optimal Algorithm for Half-plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

Visibility Queries in Simple Polygons
by: Bhore, Sujoy, et al.
Published: (2026)

Upward-Planar Drawings with Bounded Span
by: Angelini, Patrizio, et al.
Published: (2026)

Min-1-Planarity is NP-Hard
by: Okada, Yuto
Published: (2026)

Weakly Leveled Planarity with Bounded Span
by: Bekos, Michael, et al.
Published: (2024)

On Planar Straight-Line Dominance Drawings
by: Angelini, Patrizio, et al.
Published: (2025)

Clustered Planarity Variants for Level Graphs
by: Fink, Simon D., et al.
Published: (2024)

2-Layer Fan-Planarity in Polynomial Time
by: Kobayashi, Yasuaki, et al.
Published: (2025)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
by: Biedl, Therese, et al.
Published: (2026)

Morphing Planar Graph Drawings Through 3D
by: Buchin, Kevin, et al.
Published: (2022)

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
by: Iacono, John, et al.
Published: (2025)

Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
by: Klemz, Boris, et al.
Published: (2024)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
by: Afshani, Peyman, et al.
Published: (2026)

Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings
by: Dobler, Alexander, et al.
Published: (2024)

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
by: Glitzner, Frederik, et al.
Published: (2025)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
by: Maus, Victor, et al.
Published: (2026)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
by: Gribanov, D., et al.
Published: (2023)

Duality between Lines and Points
by: Saxena, Sanjeev
Published: (2025)