64 citations · 64 across the 3 of their papers we have counts for
5 papers
The Influence of Dimensions on the Complexity of Computing Decision Trees
Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani +5
A decision tree recursively splits a feature space and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machi…
Inserting one edge into a simple drawing is hard
Alan Arroyo, Fabian Klute, Irene Parada +3
A {\em simple drawing} of a graph is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge in the complement o…
Counting Triangulations and other Crossing-Free Structures Approximately
Victor Alvarez, Karl Bringmann, Saurabh Ray +1
We consider the problem of counting straight-edge triangulations of a given set of points in the plane. Until very recently it was not known whether the exact number of tri…
Upper Bound on the Number of Vertices of Polyhedra with -Constraint Matrices
Khaled Elbassioni, Zvi Lotker, Raimund Seidel
In this note we show that the maximum number of vertices in any polyhedron with -constraint matrix and a real vector is at most $d…
A better upper bound on the number of triangulations of a planar point set
Francisco Santos, Raimund Seidel
We show that a point set of cardinality in the plane cannot be the vertex set of more than straight-edge triangulations of its convex hull. This improves the p…