Approximation of planar convex sets from hyperplane probes

DOI10.1007/PL00009313MaRDI QIDQ1364138zbMATH OpenFDO

Authors O. Diekmann

Publication date 12 July 2000

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009313

zbMATH Keywords

approximation of planar convex setsgeometric probing

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Approximation by convex sets (52A27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

The following geometric probing problem is considered: An unknown planar convex set is probed by an oracle which, when given a unit vector, returns the position of the corresponding supporting hyperplane. The author presents an on-line algorithm which, after \(n\) probes, gives inscribed and circumscribed polygons with a Hausdorff distance of \(O(n^{-2})\). This is optimal and an improvement on an algorithm of \textit{M. Lindenbaum} and \textit{A. Bruckstein} [IEEE Transactions on Pattern Analysis and Machine Intelligence 10, 517-529 (1994)].

Recommendations

• Probing convex polygons with half-planes
• Model-based probing strategies for convex polygons
• Parallel strategies for geometric probing
• Reconstruction of polygons from projections
• scientific article; zbMATH DE number 177850

Cited in

(11)

• Lower bounds for \(n\)-term approximations of plane convex sets and related topics
• On computing the convex hull of (piecewise) curved objects
• Adaptive sampling for geometric problems over data streams
• Shape estimation from support and diameter functions
• Probing convex polygons with half-planes
• scientific article; zbMATH DE number 4153914 (Why is no real title available?)
• A GENERAL APPROXIMATION ALGORITHM FOR PLANAR MAPS WITH APPLICATIONS
• scientific article; zbMATH DE number 1305453 (Why is no real title available?)
• Probing a set of hyperplanes by lines and related problems
• THE STEINER CENTRE OF A SET OF POINTS: STABILITY, ECCENTRICITY, AND APPLICATIONS TO MOBILE FACILITY LOCATION
• Learning smooth shapes by probing

This page was built for publication: Approximation of planar convex sets from hyperplane probes

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