Efficient Colored Orthogonal Range Counting

DOI10.1137/070684483zbMath1187.68172OpenAlexW2081442360MaRDI 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 tradeoffmatrix multiplicationcolored orthogonal range countinggeneralized range searchingoutput-sensitive decompositionunion of orthants

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Data structures (68P05) Combinatorial complexity of geometric structures (52C45)

Related Items (16)

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

This page was built for publication: Efficient Colored Orthogonal Range Counting