Cover Image

Parameterized and approximation algorithms for coverings points with segments in the plane

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kowalska, Katarzyna, Pilipczuk, Michał
Format:	Preprint
Published:	2024
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

Parameterized dynamic data structure for Split Completion
by: Majewski, Konrad, et al.
Published: (2024)

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

The Parameterized Complexity of Extending Stack Layouts
by: Depian, Thomas, et al.
Published: (2024)

A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
by: Elkin, Yury, et al.
Published: (2021)

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Parameterized algorithms for block-structured integer programs with large entries
by: Cslovjecsek, Jana, et al.
Published: (2023)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

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

Rectangle Tiling Binary Arrays
by: Ghosal, Pratik, et al.
Published: (2020)

A face cover perspective to $\ell_1$ embeddings of planar graphs
by: Filtser, Arnold
Published: (2019)

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
by: Cabello, Sergio, et al.
Published: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Parameterized Complexity of MinCSP over the Point Algebra
by: Osipov, George, et al.
Published: (2023)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
by: Kluk, Kacper, et al.
Published: (2026)

Faster exponential algorithms for cut problems via geometric data structures
by: Kozma, László, et al.
Published: (2025)

Computing largest minimum color-spanning intervals of imprecise points
by: Acharyya, Ankush, et al.
Published: (2024)

Hashing geographical point data using the space-filling H-curve
by: Netay, Igor V.
Published: (2024)

Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
by: Berthe, Gaétan, et al.
Published: (2023)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

Feature-aware manifold meshing and remeshing of point clouds and polyhedral surfaces with guaranteed smallest edge length
by: Lipschütz, Henriette, et al.
Published: (2023)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Fast and simple multiplication of bounded twin-width matrices
by: Kozma, László, et al.
Published: (2026)

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Time complexity of the Analyst's Traveling Salesman algorithm
by: Ramirez, Anthony, et al.
Published: (2022)

Lower bounds for the universal TSP on the plane
by: Kravaris, Cosmas
Published: (2024)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

An algorithm for accurate and simple-looking metaphorical maps
by: Katsanou, Eleni, et al.
Published: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Dynamic Detours
by: Dadush, Daniel, et al.
Published: (2026)

Parameterized algorithms for $k$-Inversion
by: Antony, Dhanyamol, et al.
Published: (2026)

Minor Containment and Disjoint Paths in almost-linear time
by: Korhonen, Tuukka, et al.
Published: (2024)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)