Range searching in low-density environments

DOI10.1016/S0020-0190(96)00154-8MaRDI QIDQ1350104zbMATH OpenOpenAlexFDO

Authors Otfried Cheong, Jules Vleugels

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(96)00154-8

zbMATH Keywords

Computational geometryFat objectsLow densityMotion planningPoint locationRange searching

Mathematics Subject Classification ID

General topics in the theory of software (68N01)

Recommendations

• Range Searching and Point Location among Fat Objects
• scientific article; zbMATH DE number 1241835
• Approximate range searching
• On the difficulty of range searching.
• scientific article; zbMATH DE number 403950

Cites work

• Efficient hidden surface removal for objects with small union size
• Fat Triangles Determine Linearly Many Holes
• scientific article; zbMATH DE number 4108220 (Why is no real title available?)
• On fat partitioning, fat covering and the union size of polygons
• On the union of fat wedges and separating a collection of segments by a line
• Point location in fat subdivisions
• Range Searching and Point Location among Fat Objects
• The complexity of the free space for a robot moving amidst fat obstacles
• The complexity of the free space for motion planning amidst fat obstacles

Cited in

(15)

• Smoothed analysis of probabilistic roadmaps
• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• Models and motion planning
• Local polyhedra and geometric graphs
• Models and motion planning
• Dynamic data structures for fat objects and their applications
• Efficient image retrieval through vantage objects
• Approximating the -low-density value
• Map-matching queries under Fréchet distance on low-density spanners
• Map matching queries on realistic input graphs under the Fréchet distance
• Approximating the Fréchet distance when only one curve is c-packed
• Data structures for approximate Fréchet distance for realistic curves
• An optimal-time algorithm for shortest paths on realistic polyhedra
• On realistic terrains
• Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

This page was built for publication: Range searching in low-density environments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1350104)