Buchumschlag

Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Lynch, Jayson, Spalding-Jamieson, Jack
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Geometry
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
von: Spalding-Jamieson, Jack, et al.
Veröffentlicht: (2025)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
von: Lynch, Jayson, et al.
Veröffentlicht: (2025)

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
von: Spalding-Jamieson, Jack
Veröffentlicht: (2025)

The Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving
von: Robson, Eliot W., et al.
Veröffentlicht: (2024)

Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
von: Spalding-Jamieson, Jack, et al.
Veröffentlicht: (2025)

Morphing Planar Graph Drawings via Orthogonal Box Drawings
von: Biedl, Therese, et al.
Veröffentlicht: (2024)

Carving Polytopes with Saws in 3D
von: Robson, Eliot W., et al.
Veröffentlicht: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
von: Ebbens, Matthijs, et al.
Veröffentlicht: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
von: Kolmogorov, Vladimir, et al.
Veröffentlicht: (2026)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
von: Park, Seongbin, et al.
Veröffentlicht: (2026)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
von: Cheng, Siu-Wing, et al.
Veröffentlicht: (2025)

Fast Approximation Algorithms for Piercing Boxes by Points
von: Agarwal, Pankaj K., et al.
Veröffentlicht: (2023)

Fréchet Distance in Subquadratic Time
von: Cheng, Siu-Wing, et al.
Veröffentlicht: (2024)

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

The Presort Hierarchy for Geometric Problems
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2026)

Who Needs Crossings?: Noncrossing Linkages are Universal, and Deciding (Global) Rigidity is Hard
von: Abel, Zachary, et al.
Veröffentlicht: (2025)

All Polyhedral Manifolds are Connected by a 2-Step Refolding
von: Chung, Lily, et al.
Veröffentlicht: (2025)

Two Tiling is Undecidable
von: Stade, Jack
Veröffentlicht: (2025)

A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2025)

Linear-Time $(1+\varepsilon)$-Approximation Algorithms for Two-Line-Center Problems
von: Chung, Chaeyoon, et al.
Veröffentlicht: (2026)

Escaping a Polygon
von: Abel, Zachary, et al.
Veröffentlicht: (2020)

On Triangular Separation of Bichromatic Point Sets
von: Bergold, Helena, et al.
Veröffentlicht: (2025)

Constant Workspace Algorithms for Computing Relative Hulls in the Plane
von: Chhabra, Himanshu, et al.
Veröffentlicht: (2024)

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

Three Edge-disjoint Plane Spanning Paths in a Point Set
von: Kindermann, Philipp, et al.
Veröffentlicht: (2023)

All Polyhedral Manifolds are Connected by a 2-Step Refolding
von: Chung, Lily, et al.
Veröffentlicht: (2024)

Asymmetric Separation Problem for Bichromatic Point Set
von: Maji, Sukanya, et al.
Veröffentlicht: (2024)

The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard
von: Stade, Jack
Veröffentlicht: (2022)

Undecidability of Tiling with a Tromino
von: ULB CompGeom Group, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Anchored Multiwatchman Routes
von: Mitchell, Joseph S. B., et al.
Veröffentlicht: (2024)

On $k$-Plane Insertion into Plane Drawings
von: Katheder, Julia, et al.
Veröffentlicht: (2024)

Critical Point Extraction from Multivariate Functional Approximation
von: Ma, Guanqun, et al.
Veröffentlicht: (2024)

On Stable Approximation Algorithms for Geometric Coverage Problems
von: de Berg, Mark, et al.
Veröffentlicht: (2024)

Finding a Shortest Curve that Separates Few Objects from Many
von: Biedl, Therese, et al.
Veröffentlicht: (2025)

Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
von: Acharya, Pritam, et al.
Veröffentlicht: (2024)

Approximation Algorithms for the Freeze Tag Problem inside Polygons
von: Rajabi-Alni, Fatemeh, et al.
Veröffentlicht: (2024)

Translators Asymptotic to Planes
von: Lynch, Stephen, et al.
Veröffentlicht: (2025)

An Algorithm for Illuminating $n$ Nonoverlapping Circular Discs' Boundaries on the Plane with Application to Tree Stem Illumination Problem
von: Sukkasem, Phapaengmuang, et al.
Veröffentlicht: (2025)

Untangling Segments in the Plane
von: da Fonseca, Guilherme D., et al.
Veröffentlicht: (2025)

Long Plane Trees
von: Cabello, Sergio, et al.
Veröffentlicht: (2021)