Computer Engineering Commons^™

Complexity Of Some Geometric Problems, Marcus Schaefer

Technical Reports

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.