Efficient searching with linear constraints

DOI10.1006/jcss.2000.1709zbMath0966.68061OpenAlexW4210591609MaRDI QIDQ1591152

Paulo G. Franciosa, Lars Arge, Jeff Erickson, Jeffrey Scott Vitter, Pankaj K. Agarwal

Publication date: 2 April 2001

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1709

zbMATH Keywords

halfspace range searching

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (11)

Subquadratic algorithms for succinct stable matching ⋮ Indexing moving points ⋮ Approximate range searching in external memory ⋮ Optimal partition trees ⋮ On Dominance Reporting in 3D ⋮ Approximate Range Searching in External Memory ⋮ Cache-oblivious range reporting with optimal queries requires superlinear space ⋮ A general approach for cache-oblivious range reporting and approximate range counting ⋮ Robust shape fitting via peeling and grating coresets ⋮ Efficient searching with linear constraints ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

Cites Work

• Halfspace range search: An algorithmic application of k-sets
• The power of geometric duality
• \(\epsilon\)-nets and simplex range queries
• Maintenance of configurations in the plane
• Reporting points in halfspaces
• Efficient partition trees
• On levels in arrangements of lines, segments, planes, and triangles
• Improved bounds for planar \(k\)-sets and related problems
• Efficient searching with linear constraints
• Applications of random sampling in computational geometry. II
• Indexing for data models with constraints and classes
• Organization and maintenance of large ordered indexes
• Intersection Queries in Curved Objects
• New upper bounds for neighbor searching
• Filtering Search: A New Approach to Query-Answering
• Polygon Retrieval
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Constructing Belts in Two-Dimensional Arrangements with Applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient searching with linear constraints