1
$\begingroup$

I am a master computer science student, and I am interested in both geometry and complexity theory. So I would like to know what is the relations between discrete geometry, computer graphics, and complexity theory ?

I know the answer partially but I would like to have a clear answer since I do like to work on these fields in the future.

Thank you in advance.

$\endgroup$
-1
$\begingroup$

Have a look at this slide of David Eppstein in which he tries to draw connections between these subfields. In my opinion, a computational-geometric complexity result is likely to be confined to computational geometry itself without broadly affecting complexity theory in general.

Excerpt from the above slide: Some computational geometry problems have practical applications. Their theoretical hardness are all conjectured to be $NP$-hard but still have not been proven. Some have approximation schemes.

$\endgroup$
1
  • 1
    $\begingroup$ Please summarize the contents of the slide in your answer. At the moment, this is just a link, which could die at any time. $\endgroup$ – David Richerby Oct 14 '18 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.