Cover Image

The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Afshani, Peyman, Brodal, Gerth Stølting, Sitchinava, Nodari
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dynamic Convex Hulls for Simple Paths
by: Brewer, Bruce, et al.
Published: (2024)

Deterministic Cache-Oblivious Funnelselect
by: Brodal, Gerth Stølting, et al.
Published: (2024)

Bottom-up Rebalancing Binary Search Trees by Flipping a Coin
by: Brodal, Gerth Stølting
Published: (2024)

Engineering Fully Dynamic Convex Hulls
by: van der Hoog, Ivor, et al.
Published: (2026)

Buffered Partially-Persistent External-Memory Search Trees
by: Brodal, Gerth Stølting, et al.
Published: (2025)

Partition-based Simple Heaps
by: Brodal, Gerth Stølting, et al.
Published: (2026)

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

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
by: Iacono, John, et al.
Published: (2025)

Private Approximations of a Convex Hull in Low Dimensions
by: Gao, Yue, et al.
Published: (2020)

Efficient Parallel Algorithms for Hypergraph Matching
by: Reinstädtler, Henrik, et al.
Published: (2026)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
by: Goodrich, Michael T., et al.
Published: (2024)

2-Layer Fan-Planarity in Polynomial Time
by: Kobayashi, Yasuaki, et al.
Published: (2025)

Ranking and Unranking of the Planar Embeddings of a Planar Graph
by: Di Battista, Giuseppe, et al.
Published: (2024)

Upward-Planar Drawings with Bounded Span
by: Angelini, Patrizio, et al.
Published: (2026)

Min-1-Planarity is NP-Hard
by: Okada, Yuto
Published: (2026)

Weakly Leveled Planarity with Bounded Span
by: Bekos, Michael, et al.
Published: (2024)

On Planar Straight-Line Dominance Drawings
by: Angelini, Patrizio, et al.
Published: (2025)

Clustered Planarity Variants for Level Graphs
by: Fink, Simon D., et al.
Published: (2024)

Optimal Orthogonal Drawings in Linear Time
by: Didimo, Walter, et al.
Published: (2025)

Exact Algorithms for Clustered Planarity with Linear Saturators
by: Da Lozzo, Giordano, et al.
Published: (2024)

Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
by: Nekrich, Yakov, et al.
Published: (2026)

Morphing Planar Graph Drawings Through 3D
by: Buchin, Kevin, et al.
Published: (2022)

Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
by: Klemz, Boris, et al.
Published: (2024)

Shortest Paths on Convex Polyhedral Surfaces
by: Wang, Haitao
Published: (2025)

Online Sorting and Translational Packing of Convex Polygons
by: Aamand, Anders, et al.
Published: (2021)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

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

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

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

Dominance for Containment Problems
by: Akram, Waseem, et al.
Published: (2022)

Impossibility of Depth Reduction in Explainable Clustering
by: Deng, Chengyuan, et al.
Published: (2023)

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

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

Range Counting Oracles for Geometric Problems
by: Driemel, Anne, et al.
Published: (2025)

Algorithms for Halfplane Coverage and Related Problems
by: Wang, Haitao, et al.
Published: (2024)

Optimal Trajectories in Discrete Space with Acceleration Constraints
by: Casteigts, Arnaud, et al.
Published: (2026)

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

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

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