On constant factors in comparison-based geometric algorithms and data structures

DOI10.1007/s00454-015-9677-yzbMath1315.68251OpenAlexW2089943985MaRDI QIDQ2349854

Yanyan Li

Publication date: 18 June 2015

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10012/8783

zbMATH Keywords

convex hullmaximapoint locationbinary space partitionline segment intersectioncomparison-based algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20)

Related Items (2)

Skyline Computation with Noisy Comparisons ⋮ Faster algorithms for largest empty rectangles and boxes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multi-pass geometric algorithms
• On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• On the complexity of computations under varying sets of primitives
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• A provably fast linear-expected-time maxima-finding algorithm
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Output-sensitive results on convex hulls, extreme points, and related problems
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Median Selection Requires $(2+\epsilon)n$ Comparisons
• Persistent Predecessor Search and Orthogonal Point Location on the Word RAM
• Algorithms for Reporting and Counting Geometric Intersections
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• The Ultimate Planar Convex Hull Algorithm?
• Heaps on Heaps
• Average case selection
• A New Approach to Planar Point Location
• New Upper Bounds in Klee’s Measure Problem
• Optimal binary space partitions for orthogonal objects
• On Finding the Maxima of a Set of Vectors
• Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design
• Selecting the Median
• On the Exact Worst Case Query Complexity of Planar Point Location
• Enumerating extreme points in higher dimensions
• Binary Space Partitions of Orthogonal Subdivisions
• Optimal Expected-Case Planar Point Location
• Algorithms and Data Structures
• Orthogonal range searching on the RAM, revisited
• Automata, Languages and Programming
• A Tournament Problem

This page was built for publication: On constant factors in comparison-based geometric algorithms and data structures