arXiv preprint ·
Online geometric matching and segments block points
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given a sequence of online points in general position in the plane, the geometric matching problem asks to match as many points as possible, subject to segment crossing constraints. We initiate the study of online geometric matching with limited crosses. In the $k$-crossing model each matched segment is allowed to have at most $k$ crosses, where $k=0$ corresponds to the online noncrossing matching model for which Bose et al. proved that Greedy is an optimal deterministic algorithm achieving a competitive ratio of $2/3$. In the triangle-free-crossing model no three matched segments are allowed to pairwise cross each other. Interestingly, we show in both cases the performance of Greedy does not improve by allowing crosses, and in fact, becomes worse in the $k$-crossing setting for $k\ge 1$. In the triangle-free-crossing model, we propose a simple two-layer-Greedy deterministic algorithm achieving a competitive ratio $4/5$. More interestingly, we propose and study the underlying segments blocking points extremal problem, and discuss its connection to vertex cover numbers and Ramsey numbers, with interesting open problems that might be of independent interest. We revisit the noncrossing model. We give a randomized algorithm which is an asymmetric version of Kamali et al., improving the competitive ratio from $0.66952$ to $0.67034$. We also show, via a conceptually simple construction, that no randomized algorithm can match more than $6/7$ fraction of points, improving the previous $16/17$ by Boyar et al.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Linear Time Maximum Clique in Circular Arc Graphs
Boundary Detection for High-Dimensional Point Clouds
Navigable Graphs for Low-Dimensional Hyperbolic Spaces
Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings
CyberHull: Deterministic Malicious URL Isolation via Convex Hull
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.