Thumbnail
Access Restriction
Open

Author Hudson, Benoît ♦ Miller, Gary ♦ Phillips, Todd
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Output-sensitive Time ♦ Arbitrary Dimension ♦ Steiner Vertex ♦ Sparse Mesh ♦ Conformal Delaunay Mesh ♦ Large Class ♦ Guaranteed Mesh Size ♦ Input Feature ♦ Optimal Time Bound ♦ Quality Improvement ♦ Integer Coordinate ♦ Prescribed Element Shape Quality Bound ♦ Sparse Voronoi Refinement ♦ New Technique
Description In Symposium on Computational Geometry
a conformal Delaunay mesh in arbitrary dimension with guaranteed mesh size and quality. Our algorithm runs in output-sensitive time O(nlog(L/s) + m), with constants depending only on dimension and on prescribed element shape quality bounds. For a large class of inputs, including integer coordinates, this matches the optimal time bound of Θ(n log n + m). Our new technique uses interleaving: we maintain a sparse mesh as we mix the recovery of input features with the addition of Steiner vertices for quality improvement. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2001-01-01