Buchumschlag

Polyline Simplification has Cubic Complexity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bringmann, Karl, Chaudhury, Bhaskar Ray
Format:	Preprint
Veröffentlicht:	2018
Schlagworte:	Computational Geometry Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Dynamic and Streaming Algorithms for Union Volume Estimation
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
von: Blank, Lotte, et al.
Veröffentlicht: (2026)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

The Complexity of Geodesic Spanners
von: de Berg, Sarita, et al.
Veröffentlicht: (2023)

Knapsack with Small Items in Near-Quadratic Time
von: Bringmann, Karl
Veröffentlicht: (2023)

Space Complexity of Euclidean Clustering
von: Zhu, Xiaoyi, et al.
Veröffentlicht: (2024)

The Parameterized Complexity of Extending Stack Layouts
von: Depian, Thomas, et al.
Veröffentlicht: (2024)

On the Complexity of the Ordered Covering Problem in Distance Geometry
von: Souza, Michael, et al.
Veröffentlicht: (2025)

The Complexity of Geodesic Spanners using Steiner Points
von: de Berg, Sarita, et al.
Veröffentlicht: (2024)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Lagrangian Simulation Volume-Based Contour Tree Simplification
von: Dilys, Domantas, et al.
Veröffentlicht: (2025)

Freeze-Tag in $L_1$ has Wake-up Time Five
von: Bonichon, Nicolas, et al.
Veröffentlicht: (2024)

Extremely Scalable Distributed Computation of Contour Trees via Pre-Simplification
von: Li, Mingzhe, et al.
Veröffentlicht: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Computational Complexities of Folding
von: Eppstein, David
Veröffentlicht: (2024)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
von: Bringmann, Karl, et al.
Veröffentlicht: (2022)

Approximation Algorithms for Smallest Intersecting Balls
von: Zheng, Jiaqi, et al.
Veröffentlicht: (2024)

Light Spanners with Small Hop-Diameter
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Faster exponential algorithms for cut problems via geometric data structures
von: Kozma, László, et al.
Veröffentlicht: (2025)

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
von: Depian, Thomas, et al.
Veröffentlicht: (2025)

A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
von: Gusain, Rachana, et al.
Veröffentlicht: (2025)

Counting Unit Circular Arc Intersections
von: Wang, Haitao
Veröffentlicht: (2026)

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

Upward-Planar Drawings with Bounded Span
von: Angelini, Patrizio, 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)

On Approximating the Weighted Region Problem in Square Tessellations
von: Kakimura, Naonori, et al.
Veröffentlicht: (2024)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
von: Abrahamsen, Mikkel, et al.
Veröffentlicht: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
von: Liu, Shuilian, et al.
Veröffentlicht: (2025)

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2025)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
von: Maus, Victor, et al.
Veröffentlicht: (2026)

Online Algorithms for Geometric Independent Set
von: De, Minati, et al.
Veröffentlicht: (2026)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
von: Grandoni, Fabrizio, et al.
Veröffentlicht: (2026)

Hitting Axis-Parallel Segments with Weighted Points
von: Raman, Rajiv, et al.
Veröffentlicht: (2026)

Deterministic Volume Estimation of Truncated Hypercubes
von: Gunluk, Kyra
Veröffentlicht: (2026)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2026)

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

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
von: Huang, Lingxiao, et al.
Veröffentlicht: (2022)