0
$\begingroup$

Are spatial data structures like BVH - Bounding Volume Hierarchy ,kD-Trees etc are part of Computational Geometry( http://graphics.stanford.edu/courses/cs268-14-fall/) or of

Data structures and Algorithms( http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/index.htm ) or of

Geometric modelling( https://graphics.stanford.edu/courses/cs348a-12-winter/ ) ?

If Spatial data structures are not part of neither of these 3, Can you tell which branch of computer science deals with the spatial data structures?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ They probably lie at the intersection of all three. Why does it matter? They will be covered at every course in which they are relevant. $\endgroup$
    – Yuval Filmus
    May 19, 2015 at 4:14
  • 2
    $\begingroup$ If you are asking whether they are part of those 3 specific courses at MIT/Stanford, you should read the syllabus; that question is not on-topic here. If you are asking about whether they are part of Computational Geometry courses (etc.) in general, that will depend upon the specific course -- and that's also not on-topic here. This site is for answerable technical questions about computer science. $\endgroup$
    – D.W. ♦
    May 19, 2015 at 6:30

1 Answer 1

Reset to default
2
$\begingroup$

You need spatial data structures as part of computational geometry, to have at least some reasonable base reference against which to compare the time and memory consumption of special purpose (sweepline/randomized) algorithm. For this purpose, BVH is too vaguely defined to be useful (except for summarizing a common principle for some better specified data structures), but kD-trees are good enough for this purpose.

I don't see where you would need spatial data structures for non-geometry related data structures and algorithms, so I would say it is only a part of it, if you study geometry (or GIS) related problems. But if anybody shows me a non-geometry related application, then I'm quite willing to change my mind.

For geometric modeling, things like constructive solid geometry, homogeneous coordinates, Bézier curves, B-splines and NURBS should come first, because understanding them is also important when just using existing geometry modeling software. But BVH fits in well, because it is an intuitive geometric concept. It can sometimes be useful for understanding the performance behavior of existing geometry modeling software (sometimes the user can even influence the BVH to improve performance). I see fewer reasons why kD-trees should be part of geometric modeling.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer. I have one more question - Data structures like BVH, kD-trees etc are called "Geometric Algorithms" ? $\endgroup$
    – Mr.Grey
    May 19, 2015 at 8:41
  • $\begingroup$ @Mr.Grey Why do you think that a "data structure" is called an "algorithm"? I'd rather say that some geometric algorithms will use such data structures, so you have to talk about the data structure, in order to be able to talk about the algorithm. That's part of what I meant when I said that these data structures are part of computational geometry! $\endgroup$
    – Thomas Klimpel
    May 19, 2015 at 8:49
  • $\begingroup$ Thanks again! - So data structures is a complete separate field and Computational geometry uses those data structures to design and analyze geometric algorithms? $\endgroup$
    – Mr.Grey
    May 19, 2015 at 8:59
  • $\begingroup$ @Mr.Grey The field is called computational geometry, and analyzes both data structures and algorithms. The meaning of "data structure" is quite well defined, no need to muddle with its meaning by calling it algorithm. The meaning of "algorithm" is more difficult, because good algorithm design is modular, but what it the actual algorithm, if all of its parts can be exchanged. (You want to have the parts exchangable, so that you can better test and debug your implementation, especially when things go wrong...) $\endgroup$
    – Thomas Klimpel
    May 19, 2015 at 10:03

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