Decision Trees for Geometric Models
From MaRDI portal
Publication:4513214
DOI10.1142/S0218195998000175zbMath1035.68521MaRDI QIDQ4513214
Joseph S. B. Mitchell, David Rappaport, Esther M. Arkin, Steven S. Skiena, Henk G. Meijer
Publication date: 7 November 2000
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Computational aspects related to convexity (52B55) Computing methodologies for image processing (68U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
On the hardness of the minimum height decision tree problem ⋮ Almost optimal set covers in finite VC-dimension ⋮ Searching in random partially ordered sets ⋮ Decision trees for function evaluation: simultaneous optimization of worst and expected cost ⋮ Theoretical analysis of git bisect ⋮ Approximating optimal binary decision trees ⋮ Queries revisited. ⋮ A note on data structures for maintaining bipartitions ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ The binary identification problem for weighted trees ⋮ On Polynomial Time Constructions of Minimum Height Decision Tree ⋮ Exact Learning of Discretized Geometric Concepts
Cites Work
- How to draw a planar graph on a grid
- Simplified linear-time Jordan sorting and polygon clipping
- Determining the shape of a convex n-sided polygon by using \(2n+k\) tactile probes
- Optimal packing and covering in the plane are NP-complete
- Model-based probing strategies for convex polygons
- Approximation algorithms for combinatorial problems
- Constructing optimal binary decision trees is NP-complete
- Probing polygons minimally is hard
- Almost optimal set covers in finite VC-dimension
- Decision tree design from a communication theory standpoint
- How to find a battleship
- Planar Formulae and Their Uses
- An optimal algorithm for intersecting line segments in the plane
- Sorting jordan sequences in linear time using level-linked search trees