Document Type
Article
Publication Date
10-2008
Abstract
We show that recognizing intersection graphs of convex sets has the same complexity as deciding truth in the existential first-order theory of the reals. Comparing this to similar results on the rectilinear crossing number and intersection graphs of line segments, we argue that there is a need to recognize this level of complexity as its own class.
Recommended Citation
Schaefer, Marcus. (2008) Complexity of Some Geometric Problems.
https://via.library.depaul.edu/tr/9
Included in
Technical Report Number
08-009