Cover Image

Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Spalding-Jamieson, Jack, Naredla, Anurag Murty
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
by: Lynch, Jayson, et al.
Published: (2025)

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
by: Spalding-Jamieson, Jack
Published: (2025)

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

Morphing Planar Graph Drawings via Orthogonal Box Drawings
by: Biedl, Therese, et al.
Published: (2024)

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

Carving Polytopes with Saws in 3D
by: Robson, Eliot W., et al.
Published: (2024)

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

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

An Improved Bound for Plane Covering Paths
by: Akitaya, Hugo A., et al.
Published: (2025)

Improved Lower Bound on the Number of Pseudoline Arrangements
by: Dallant, Justin
Published: (2024)

Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
by: Abrahamsen, Mikkel, et al.
Published: (2025)

Morphing Graph Drawings in the Presence of Point Obstacles
by: Firman, Oksana, et al.
Published: (2023)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

The Presort Hierarchy for Geometric Problems
by: van der Hoog, Ivor, et al.
Published: (2026)

Two Tiling is Undecidable
by: Stade, Jack
Published: (2025)

An Improved Lower Bound on the Number of Pseudoline Arrangements
by: Kühnast, Fernando Cortés, et al.
Published: (2024)

A Hierarchical Heuristic for Clustered Steiner Trees in the Plane with Obstacles
by: Parque, Victor
Published: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

On Triangular Separation of Bichromatic Point Sets
by: Bergold, Helena, et al.
Published: (2025)

The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics
by: Nikoleit, Henri, et al.
Published: (2026)

Three Edge-disjoint Plane Spanning Paths in a Point Set
by: Kindermann, Philipp, et al.
Published: (2023)

Asymmetric Separation Problem for Bichromatic Point Set
by: Maji, Sukanya, et al.
Published: (2024)

The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard
by: Stade, Jack
Published: (2022)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)

New Lower Bound and Algorithms for Online Geometric Hitting Set Problem
by: De, Minati, et al.
Published: (2024)

Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds
by: Chung, Jaehoon
Published: (2026)

On $k$-Plane Insertion into Plane Drawings
by: Katheder, Julia, et al.
Published: (2024)

Some Lower Bounds on the Reach of an Algebraic Variety
by: La Valle, Chris, et al.
Published: (2024)

Improved Bounds for Discrete Voronoi Games
by: de Berg, Mark, et al.
Published: (2026)

Bounding a Polygon by a Minimum Number of Vertices
by: Abrahamsen, Mikkel, et al.
Published: (2025)

Realizing Metric Spaces with Convex Obstacles
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

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

Disk and Partial Disk Inspection: Worst- to Average-Case and Pareto Upper Bounds
by: Conley, James, et al.
Published: (2024)

Untangling Segments in the Plane
by: da Fonseca, Guilherme D., et al.
Published: (2025)

Long Plane Trees
by: Cabello, Sergio, et al.
Published: (2021)

Improved Bound on the Number of Pseudoline Arrangements via the Zone Theorem
by: Dallant, Justin
Published: (2025)

Undecidability of Translational Tiling of the Plane with Four Tiles
by: Yang, Chao, et al.
Published: (2025)

Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
by: Barequet, Gill, et al.
Published: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Covering half-grids with lines and planes
by: Bishnoi, Anurag, et al.
Published: (2025)