Quasi-optimal upper bounds for simplex range searching and new zone theorems (Q1201746)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Quasi-optimal upper bounds for simplex range searching and new zone theorems |
scientific article; zbMATH DE number 98404
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Quasi-optimal upper bounds for simplex range searching and new zone theorems |
scientific article; zbMATH DE number 98404 |
Statements
Quasi-optimal upper bounds for simplex range searching and new zone theorems (English)
0 references
17 January 1993
0 references
This is a fundamental study of range searching in fixed dimensional Euclidean space. The basic problem is to count or report points lying inside a given query simplex (preprocessing is allowed and required). Algorithms with almost tight complexity bounds are developed in fixed \(d\) dimensions, and fine-tuned in 2- and 3-space. As a consequence new improved zone theorems on hyperplane arrangements are obtained in two and three dimensions.
0 references
computational geometry
0 references
range searching
0 references
complexity
0 references
0 references
0.8293442726135254
0 references
0.8287614583969116
0 references
0.8285298347473145
0 references
0.8212461471557617
0 references
