2
$\begingroup$

I have a computer engineering degree and i am very interested in theoretical and combinatorial aspects of computational geometry .

I want to build the mathematical foundation for this area so i can apply for a decent research based postgraduate program .

My question is : What topics in math should I study to prepare for this goal?

thank you

$\endgroup$
  • 1
    $\begingroup$ you may want to check similar questions posted on cstheory first: 1, 2, 3, 4. I don't think the answer would be much different, so IMO this should be closed as duplicate. $\endgroup$ – Kaveh Nov 28 '11 at 6:59
  • $\begingroup$ thank you for your fast response . i am just trying to focus on mathematical topics related to combinatorial and theoretical aspects of computational geometry $\endgroup$ – Akram Hassan Nov 28 '11 at 7:28
  • 1
    $\begingroup$ it doesn't matter that much which topic you are interested in, as mathematical foundations for an undergraduate looking to go to grad school the answers are similar. If you want something more then start reading research papers of your favorite researchers in CG and see what you don't understand in them and then learn what you need to understand them. $\endgroup$ – Kaveh Nov 28 '11 at 7:40
  • $\begingroup$ While I'm not sure about whether to close, I did read the answers in the linked related questions, and I think a slight rephrasing of the question might yield good specific answers. That is, it's reasonable to ask if there's any geometry-SPECIFIC math that wouldn't ordinarily be part of a general TCS-focused math curriculum. $\endgroup$ – Suresh Venkat Nov 28 '11 at 8:26
8
$\begingroup$

That really depends on the specific brand of "theoretical and combinatorial aspects of computational geometry" you're most interested in. Any mathematical background has a strong potential to pay off in future research. Moreover, the best topics to study to master existing research is not necessarily the same as the best topics to study to generate new research.

To Suresh's excellent list, I would add linear algebra, combinatorics, graph theory, convex geometry, non-Euclidean geometry, differential topology, probability, statistics, optimization, logic, abstract algebra, category theory, randomized algorithms, approximation algorithms, online algorithms, data structures, and computational complexity. And a little computer graphics, animation, robotics, learning, vision, scientific computing, scheduling, VLSI design, compiler optimization, databases, distributed computing, ad hoc networking, sensor networking, game theory, signal processing, cartography, and graphic design wouldn't hurt, either.

Or to put it more simply: Everything.

Obviously you can't actually learn everything, unless you're Terry Tao. Where you should focus first depends on your specific strengths and interests. If you have a specific topic in mind, it's probably best to jump straight into some recent research papers and work your way backward to the specific background you need. (Got a nail? Look for hammers.) Conversely, if there's a particular area of mathematics you find appealing, study that area deeply and work your way forward to research applications. (Got a hammer? Look for nails.) Or best of all, work from both ends.

So... what do you like?

$\endgroup$
  • $\begingroup$ thank you for the response , so "what do i like ? " . unfortunately i don't have a proper answer about that question . but roughly speaking i love visual problems with standard geometric objects especially : polygons , convex hulls , circles ..... etc and i love plane geometry and trignonometry as well . $\endgroup$ – Akram Hassan Nov 28 '11 at 22:31
12
$\begingroup$

I'm going to answer a slightly different question (as indicated in my comment):

Is there specific mathematical background that would help prepare for a graduate degree in TCS that focuses on computational geometry?

I have found (from conversations with other TCSers) that some kinds of geometric intuition are unfamiliar, so the best kind of background will help you in that regard. A comprehensive list along these lines would include:

  • Topology (point-set, combinatorial and algebraic)
  • Differential geometry (and some basic Riemannian geometry as well)
  • Convex analysis (especially duality)
  • Some basics in algebraic geometry (at least polynomials)
  • Basic functional analysis (normed spaces, Hilbert spaces, etc)

All of these tools show up in computational geometry nowadays on a regular basis, and their use will only get more sophisticated with time.

p.s As an aside, if you have a computer engineering degree, it's possible that your background in core theoryCS is weaker than if you had a straight-up CS degree (because of the emphasis on the EE side of things). If that's the case, then the material in the links provided by Kaveh will be immensely useful, probably more so than this list.

$\endgroup$

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.