Realistic input models for geometric algorithms

DOI10.1007/S00453-002-0961-XzbMATH Open1017.68141OpenAlexW1979838628MaRDI QIDQ1849788FDOQ1849788

Authors: Matthew J. Katz, Mark de Berg, A. Frank van der Stappen, Jules Vleugels 

Publication date: 1 December 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/18742

Recommendations

• On realistic terrains
• Guarding scenes against invasive hypercubes.
• Two design principles of geometric algorithms in finite-precision arithmetic
• Reliable and Efficient Geometric Computing
• Reliable and Efficient Computational Geometry Via Controlled Perturbation

zbMATH Keywords

analysis of algorithmscomputational geometryinput models

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (32)

• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
• An optimal-time algorithm for shortest paths on realistic polyhedra
• On realistic terrains
• Approximating the packedness of polygonal curves
• COMPUTING PUSH PLANS FOR DISK-SHAPED ROBOTS
• Tight lower bounds for halfspace range searching
• Reprint of: Bounding the locus of the center of mass for a part with shape variation
• Models and motion planning
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Approximating the \(\lambda \)-low-density value
• Approximate Range Searching in External Memory
• Delaunay Triangulation of Imprecise Points Simplified and Extended
• Guarding scenes against invasive hypercubes.
• Spanning trees crossing few barriers
• Bounding the locus of the center of mass for a part with shape variation
• Title not available (Why is that?)
• Balanced line separators of unit disk graphs
• Space complexity of exact discrete geodesic algorithms on regular triangulations
• A note on the perimeter of fat objects
• Online geometric covering and piercing
• Approximating the Fréchet distance for realistic curves in near linear time
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Computing the visibility map of fat objects
• Union of random Minkowski sums and network vulnerability analysis
• Decompositions and boundary coverings of non-convex fat polyhedra
• Approximate range searching using binary space partitions
• Maximum matchings in geometric intersection graphs
• Smoothed analysis of probabilistic roadmaps
• The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains
• Connect the Dot: Computing Feed-Links with Minimum Dilation
• Approximating the Packedness of Polygonal Curves
• I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions

This page was built for publication: Realistic input models for geometric algorithms

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