Efficient Colored Orthogonal Range Counting

DOI10.1137/070684483zbMath1187.68172MaRDI QIDQ3631900

Natan Rubin, Elad Verbin, Haim Kaplan, Micha Sharir

Publication date: 22 June 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070684483

zbMATH Keywords

time-space tradeoff; matrix multiplication; colored orthogonal range counting; generalized range searching; output-sensitive decomposition; union of orthants

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

52C35: Arrangements of points, flats, hyperplanes (aspects of discrete geometry)

68P05: Data structures

52C45: Combinatorial complexity of geometric structures

Related Items

Tight lower bounds for the size of epsilon-nets, Monomial Tropical Cones for Multicriteria Optimization, Maximal Empty Boxes Amidst Random Points, Adaptive data structures for 2D dominance colored range counting, On the representation of the search region in multi-objective optimization, Colored range queries and document retrieval, A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space, A box decomposition algorithm to compute the hypervolume indicator, On the number of maximum empty boxes amidst \(n\) points, Efficient computation of the search region in multi-objective optimization, Data structures for categorical path counting queries, Variations of largest rectangle recognition amidst a bichromatic point set, Representing the nondominated set in multi-objective mixed-integer programs, Near-linear approximation algorithms for geometric hitting sets, Colored top-\(K\) range-aggregate queries, Counting Colours in Compressed Strings