Guarding scenes against invasive hypercubes.

DOI10.1016/S0925-7721(03)00016-6MaRDI QIDQ1405005zbMATH OpenOpenAlexFDO

Authors Haggai David, Matthew J. Katz, Mark H. Overmars, A. Frank van der Stappen, Jules Vleugels, Mark de Berg

Publication date 25 August 2003

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0925-7721(03)00016-6

zbMATH Keywords

Epsilon-netsGeometric algorithmsGuarding setsInput models

Mathematics Subject Classification ID

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

Review text

In recent years realistic input models for geometric algorithms have been studied. The most important models are fathness, low density, undutteredness and small simple-cover complexity. The authors show that guardable scenes fit in between undutteredness and small simple-cover complexity. Properties of guardable scenes and heuristic algorithms to compute small guarding sets are given.

Recommendations

• Triangulating and guarding realistic polygons
• scientific article; zbMATH DE number 4213488
• Realistic input models for geometric algorithms
• Improved approximation algorithms for geometric set cover
• Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects

Cites work

• -nets and simplex range queries
• Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects
• scientific article; zbMATH DE number 431986 (Why is no real title available?)
• Linear size binary space partitions for uncluttered scenes
• Models and motion planning
• Models and motion planning
• Range Searching and Point Location among Fat Objects
• Realistic input models for geometric algorithms
• The complexity of the free space for motion planning amidst fat obstacles

Cited in

(11)

• Kinetic collision detection for convex fat objects
• Decompositions and boundary coverings of non-convex fat polyhedra
• Models and motion planning
• Realistic input models for geometric algorithms
• Approximate range searching using binary space partitions
• Delaunay Triangulation of Imprecise Points Simplified and Extended
• Triangulating and guarding realistic polygons
• Approximate Range Searching in External Memory
• Binary plane partitions for disjoint line segments
• Approximate range searching in external memory
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended

This page was built for publication: Guarding scenes against invasive hypercubes.

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