Multidimensional divide-and-conquer

DOI10.1145/358841.358850zbMath0434.68049OpenAlexW2128703518MaRDI QIDQ148390

Jon Louis Bentley, Jon Louis Bentley

Publication date: April 1980

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/358841.358850

zbMATH Keywords

analysis of algorithms data structures computational geometry range searching algorithmic paradigms empirical cumulative distribution functions closest-point problems maxima problems multidimensional searching problems

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99)

Related Items

An algorithm for handling many relational calculus queries efficiently., Optimal $L_2$-norm empirical importance weights for the change of probability measure, The searching over separators strategy to solve some NP-hard problems in subexponential time, Optimal external memory planar point enclosure, A localized meshless approach for modeling spatial-temporal calcium dynamics in ventricular myocytes, The shortest-path problem with resource constraints with $(k, 2)$-loop elimination and its application to the capacitated arc-routing problem, Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors, Dynamic range majority data structures, Faster subsequence recognition in compressed strings, On the Complexity of Closest Pair via Polar-Pair of Point-Sets, Computing on a free tree via complexity-preserving mappings, In-place algorithms for computing (Layers of) maxima, An optimized divide-and-conquer algorithm for the closest-pair problem in the planar case, Fractional cascading. II: Applications, EXTERNAL MEMORY ORTHOGONAL RANGE REPORTING WITH FAST UPDATES, A Monte Carlo strategy for data-based mathematical modeling, FAST SOFTWARE FOR BOX INTERSECTIONS, Improved quick hypervolume algorithm, On O($\sqrt{n})$ time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors, Boundary estimation from point clouds: algorithms, guarantees and applications, An O(n log n) algorithm for the all-nearest-neighbors problem, Structure and algorithms of SL-AV atmosphere model parallel program complex, Space Efficient Multi-dimensional Range Reporting, Ordered theta graphs, MEPDF: Multivariate empirical density functions, K-dominance in multidimensional data: theory and applications, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, Efficient range searching for categorical and plain data, Finding top-$k$ longest palindromes in substrings, Faster output-sensitive skyline computation algorithm, A new coding-based algorithm for finding closest pair of vectors, An Improved Vectorization Algorithm to Solve the d-MP Problem, A disk-aware algorithm for time series motif discovery, An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³, Unnamed Item, Dynamic orthogonal range queries in OLAP., Noisy colored point set matching, Space and time optimal algorithms for a class of rectangle intersection problems, A condition for the identification of multivariate models with binary instruments, Biased range trees, Maxima-finding algorithms for multidimensional samples: A two-phase approach, Dominance in the presence of obstacles, Simplex Range Searching and Its Variants: A Review, Unnamed Item, On the angle restricted nearest neighbor problem, Dynamic and internal longest common substring, Permutation inversions and multidimensional cumulative distribution functions, Polygonal intersection searching, On the equivalence of some rectangle problems, Computing the relative neighborhood graph in the $L_ 1$ and L//infinity metrics, On closest pair in Euclidean metric: monochromatic is as hard as bichromatic, Using persistent data structures for adding range restrictions to searching problems, Integrating Pareto optimization into dynamic programming, Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers, Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers, Fast multivariate empirical cumulative distribution function with connection to kernel density estimation, On the parallel-decomposability of geometric problems, Learning Binary Hash Codes for Large-Scale Image Search, Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster, Robust weighted Gaussian processes, Fast linear expected-time algorithms for computing maxima and convex hulls, The slab dividing approach to solve the Euclidean $P$-center problem, OPTIMAL RANGE MAX DATACUBE FOR FIXED DIMENSIONS, The average performance analysis of a closest‐pair algorithm, Robust Monte Carlo localization for mobile robots, A deterministic skip list for $k$-dimensional range search, Linear space data structures for two types of range search, Stabilized branch-and-price algorithms for vector packing problems, Gathering in the plane of location-aware robots in the presence of spies, Internal dictionary matching, Semi-local longest common subsequences in subquadratic time, Orthogonal range searching in linear and almost-linear space, A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES, Light orthogonal networks with constant geometric dilation, A general framework for efficient clustering of large datasets based on activity detection, Approximate colored range and point enclosure queries, On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic, A New Lower Bound for Semigroup Orthogonal Range Searching, Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model, Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy, A FAST ALGORITHM FOR COMPUTING SAMPLE ENTROPY, Accounting for Factor Variables in Big Data Regression, Minmax regret $k$-sink location on a dynamic path network with uniform capacities, An application of $m$-ary trees to the design of data structures for geometric searching problems, A data structure for dynamic range queries, K-Dominance in Multidimensional Data: Theory and Applications, Extending range queries and nearest neighbors, Multivariate analysis of orthogonal range searching and graph distances, On the Complexity of Closest Pair via Polar-Pair of Point-Sets, Average stretch factor: how low does it go?, A parallel algorithm to solve the stable marriage problem, Efficient splitting and merging algorithms for order decomposable problems., On the average length of Delaunay triangulations, On the definition and computation of rectilinear convex hulls, Dominance Product and High-Dimensional Closest Pair under L_infty, MEPDF