Model-based probing strategies for convex polygons

DOI10.1016/0925-7721(92)90023-LMaRDI QIDQ1208433zbMATH OpenOpenAlexFDO

Authors Eugene Joseph, Steven Skiena

Publication date 16 May 1993

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(92)90023-l

zbMATH Keywords

convex polygonfinger probesgeometric probingline probeslower bounds

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Analysis of algorithms and problem complexity (68Q25)

Review text

Geometric probing studies the power of different sensor models for reconstructing geometric objects. The authors seek probing strategies which completely determine a convex polygon. They use finger probes, where such probes measure the first point of contact between a direct line and the polygon. They are concerned with identifying an object and its orientation from a finite, predefined set of possible objects and they prove that \(n+4\) such finger probes are sufficient and \(n-1\) probes are necessary (optimal!) to determine the shape of a convex \(n\)-gon from a finite collection of models. For line probes they prove that \(2n+4\) probes are sufficient and \(2n-3\) necessary. The lower bound proof for line probes requires an exponential number of models. In the conclusions the authors give some interesting open problems, for instance the problem of model-based probing strategies.

Recommendations

• Probing convex polygons with half-planes
• EFFICIENT APPROXIMATION OF CONVEX POLYGONS
• An improved on-line strategy for exploring unknown polygons
• Non-interactive geometric probing: Reconstruction non-convex polygons
• scientific article; zbMATH DE number 701117
• Probing convex polygons with a wedge
• Fast computation of the modality of polygons
• Probing a scene of nonconvex polyhedra

Cites work

• An Optimal-Time Algorithm for Slope Selection
• Determining the shape of a convex n-sided polygon by using \(2n+k\) tactile probes
• Non-convex contour reconstruction
• Probing convex polygons with half-planes
• Reconstruction of polygons from projections
• Shape from probing
• The maximum number of unit distances in a convex n-gon

Cited in

(10)

• Determining the shape of a convex n-sided polygon by using \(2n+k\) tactile probes
• Reconstruction of polygons from projections
• Probing a scene of nonconvex polyhedra
• Testing geometric objects
• Approximation of planar convex sets from hyperplane probes
• Probing polygons minimally is hard
• Probing convex polygons with half-planes
• Shape from probing
• Decision Trees for Geometric Models
• Point probe decision trees for geometric concept classes

This page was built for publication: Model-based probing strategies for convex polygons

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