Cover Image

Nearly-Tight Bounds for Vertical Decomposition in Three and Four Dimensions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agarwal, Pankaj K., Ezra, Esther, Sharir, Micha
Format:	Preprint
Published:	2026
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane
by: Agarwal, Pankaj K., et al.
Published: (2024)

Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
by: Agarwal, Pankaj K., et al.
Published: (2022)

Dynamic Nearest-Neighbor Searching Under General Metrics in ${\mathbb R}^3$ and Its Applications
by: Agarwal, Pankaj K., et al.
Published: (2026)

Covering points by hyperplanes and related problems
by: Patáková, Zuzana, et al.
Published: (2024)

Implicit representations via the polynomial method
by: Cardinal, Jean, et al.
Published: (2026)

Near-Optimal Min-Sum Motion Planning in a Planar Polygonal Environment
by: Agarwal, Pankaj K., et al.
Published: (2025)

Tight Bounds on the Number of Closest Pairs in Vertical Slabs
by: Biniaz, Ahmad, et al.
Published: (2025)

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
by: Agarwal, Pankaj K., et al.
Published: (2018)

Apple-Peel Unfolding in Three and Four Dimensions: Spiral and Zonal Selection Rules
by: Yoshino, Takashi, et al.
Published: (2026)

Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
by: Aronov, Boris, et al.
Published: (2019)

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

Nearly-Tight Bounds for Zonotope Containment and Beyond
by: Eisenbrand, Friedrich, et al.
Published: (2026)

Fast Approximation Algorithms for Piercing Boxes by Points
by: Agarwal, Pankaj K., et al.
Published: (2023)

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

Optimal Motion Planning for Two Square Robots in a Rectilinear Environment
by: Agarwal, Pankaj K., et al.
Published: (2026)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

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

Fukaya-Yamaguchi Conjecture in Dimension Four
by: Bruè, Elia, et al.
Published: (2025)

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs
by: Bose, Prosenjit, et al.
Published: (2025)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)

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

Lipschitz Decompositions of Finite $\ell_{p}$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2025)

On the Largest Convexity Number of Co-Finite Sets in the Plane
by: Keller, Chaya, et al.
Published: (2026)

Complements of finite unions of convex sets
by: Keller, Chaya, et al.
Published: (2025)

An $(\aleph_0,k+2)$-Theorem for $k$-Transversals
by: Keller, Chaya, et al.
Published: (2023)

Tiling with Three Polygons is Undecidable
by: Demaine, Erik D., et al.
Published: (2024)

Geometry and Analysis of Gradient Ricci Solitons in Dimension Four
by: Cao, Xiaodong, et al.
Published: (2024)

MiGumi: Making Tightly Coupled Integral Joints Millable
by: Ganeshan, Aditya, et al.
Published: (2025)

On Minimum CADs for Algebraic Sets in Dimension Three
by: Michel, Lucas
Published: (2026)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
by: van Renssen, Andrè, et al.
Published: (2022)

On Small Pair Decompositions for Point Sets
by: Buchin, Kevin, et al.
Published: (2026)

Well-Separated Pairs Decomposition Revisited
by: Har-Peled, Sariel, et al.
Published: (2025)

Which Vertical Graphs are Non VPHT Reconstructible?
by: Gutzeit, Jette, et al.
Published: (2026)

Minimizing Vertical Length in Linked Bar Charts
by: Broek, Steven van den, et al.
Published: (2025)

Computing the Fréchet Distance When Just One Curve is $c$-Packed: A Simple Almost-Tight Algorithm
by: Conradi, Jacobus, et al.
Published: (2025)

Topological Obstructions to the Existence of Compact Shrinking Ricci Solitons in Dimension Four
by: MacMahon, Cameron
Published: (2024)

Generalized k-Cell Decomposition for Visibility Planning in Polygons
by: Bahoo, Yeganeh, et al.
Published: (2025)