Decision Trees for Geometric Models

DOI10.1142/S0218195998000175MaRDI QIDQ4513214zbMATH OpenFDO

Authors Esther M. Arkin, Joseph S. B. Mitchell, David Rappaport, Henk Meijer, Steven Skiena

Publication date 7 November 2000

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0218195998000175

zbMATH Keywords

computer visionprobing

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10)

Recommendations

• Point probe decision trees for geometric concept classes
• Decision trees: Old and new results.
• scientific article; zbMATH DE number 3986662
• The complexity of recognizing polyhedral scenes
• Model-based probing strategies for convex polygons

Cites work

• Almost optimal set covers in finite VC-dimension
• An optimal algorithm for intersecting line segments in the plane
• Approximation algorithms for combinatorial problems
• Constructing optimal binary decision trees is NP-complete
• Decision tree design from a communication theory standpoint
• Determining the shape of a convex n-sided polygon by using \(2n+k\) tactile probes
• How to draw a planar graph on a grid
• How to find a battleship
• Model-based probing strategies for convex polygons
• Optimal packing and covering in the plane are NP-complete
• Planar Formulae and Their Uses
• Probing polygons minimally is hard
• Simplified linear-time Jordan sorting and polygon clipping
• Sorting jordan sequences in linear time using level-linked search trees

Cited in

(17)

• Queries revisited.
• Decision trees for function evaluation: simultaneous optimization of worst and expected cost
• The binary identification problem for weighted trees
• On the hardness of the minimum height decision tree problem
• Almost optimal set covers in finite VC-dimension
• Approximating optimal binary decision trees
• scientific article; zbMATH DE number 4044999 (Why is no real title available?)
• Exact Learning of Discretized Geometric Concepts
• Improved approximation algorithms for the average-case tree searching problem
• Point probe decision trees for geometric concept classes
• On Polynomial Time Constructions of Minimum Height Decision Tree
• Searching in random partially ordered sets
• Theoretical analysis of git bisect
• Theoretical Analysis of Git Bisect
• Partial order multiway search
• Geometric problems in machine learning
• A note on data structures for maintaining bipartitions

This page was built for publication: Decision Trees for Geometric Models

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