Talk:Computational geometry

Comment

This is my version of a long stub. Someone else should fill in the details, I'm not a specialist. Loisel 00:38 Jan 31, 2003 (UTC)

Useful and useless links

Just a short comment on the link "Geomtry in action": 99% of the links on the "Geomtry in action" - Site are dead. I know, a link like "Geometry in action" sounds good, but it's useless if none of the links on a site dedicated to collecting links works. I suggest deleting the "Geomtry in action" - Link. — Preceding unsigned comment added by 194.138.39.59 (talk) 12:19, 27 April 2012 (UTC)

Books added

hello- I just added four references for books on the topic. two points to note.

• • One, I'm not sure that the last book by O'Rourke belongs there, as it's the only non general book on the topic, still, I found it very useful to my understanding of computational geometry
  • Two, Maybe we could list title's ISBNs and compress authorship a bit somehow? I'm not sure about citation conventions, if someone wants to fix it up, that would be great

If someone disagrees, and feels such information doesn't have a place here ( it goes go out of date quickly) -- by all means, pull it out, but it's handy to point readers to more external sources of information, IMHO.

• • • Also -- more external website links would be useful, if anyone is so inclined.

---

• O'Rourke's book is a good general reference if you remove all the code; it should stay, IMO.

• I put the references in a more academic style and wikified them. See Wikipedia:Cite_sources for a reference on these BibTeX-style citations. In my opinion, one shouldn't go to great lengths to keep a citation short -- I see thorough citation as an essential part of any academic community, although exceptions must be made. I say that having cited cell biology papers with > 50 authors. groan!

• Godfried Toussaint's webpage has some decent-to-good Java tutorials on various problems that he has students do for projects. I won't put a link to it because (a) I don't know how much interest there would be and (b) he was my prof, so there's a bit of bias, but if someone else thinks it should be linked, by all means put it up!

Adking80 22:03, 14 May 2005 (UTC)

Merge proposal

• Oppose. to merge List of books in computational geometry here. It is not a simple bibliography. It is a list with annotations. We have quite a few separate lists of books. It makes sense to merge articles accidentally started by several people on the same topic or to merge some unimportant issues that do not really warrant a separate article. Keeping the dicussed pages separately does not hinder understanding of the main topic in any way: the list is just one click away. The supporters of merging may look at it in this way: the "list of books" page is a merge of several separate small articles for individual books. I hope it will make you feel better. `'mikka 01:19, 13 January 2007 (UTC)

Split proposal

Mikkalai, thanks for changing the 3 branches to only 2. And I have no intention to start "moving other topics elsewhere" without a lot of discussion. That's why I placed the proposal in the article, and started this discussion here. Now, we only have 2 b Therefore, I agree that this article should not be split, but I believe that the division using the two terms that occur only in Wikipedia is not adequate. It leads the reader to believe that the separation into these two branches is widely accepted, but in fact it is only the way by which the wikipedia article is organized. I think that a broad description of computational geometry, followed by several examples, with some explanation of the different "flavors" they have, is better. Let's see if more people give feedback and we can decide what to do about it. Gfonsecabr 21:02, 8 April 2007 (UTC)ranches (unless someone oposes and recreates the 3rd one): Combinatorial Computational Geometry and Numerical Computational Geometry. I agree with you that "Numeri Are there any references that divide computational geometry into the 3 areas listed in this article? Essentially all the modern use I see of computational geometry refers to what is described as combinatorial computational geometry. Therefore, I believe this page should talk only about what is described as combinatorial computational geometry. The other topics can be moved to other pages (as stubs, since there is very little information anyway). Gfonsecabr 02:06, 8 April 2007 (UTC)

First of all, if you are asking this question, then probably you are not in a position to have an educated opinon.

Now as to answers: Yes there are references that distinguish different uses of the term "computational geometry", starting from the seminal book by Preparata and Shamos. What is more, there are books in these different topics under the same name. Third, before starting moving "other topics elsewhere, you must write more than one sentence. Finaly, fourth, "numerical geometry" is not an established discipline to write such article. The term does exist and seen in google, but this is mostly not what the current article about. `'mikka 18:52, 8 April 2007 (UTC)cal Geometry" is not an established discipline. I believe you changed it to "Numerical Computational Geometry" which is not established with this name either: if you google either "numerical computational geometry" or "combinatorial computational geometry" you will only find this wikipedia article (and copies of it)!

I believe that most of what is considered computational geometry nowadays fits in the Combinatorial Computational Geometry branch. Nevertheless, I also agree with Goodman and O'Rourke preface to Handbook of Discrete and Computational Geometry, which says:

..."computational geometry," which referred not long ago to simply the design and analysis of geometric algorithms, has in recent years broadened its scope, and now means the study of geometric problems from a computational point of view, including also computational convexity, computational topology, and questions involving the combinatorial complexity of arrangements and polyhedra

Problems with definition of computational geometry

The proposed in the article definition of computational geometry as study of algorithms to solve problems stated in the terms of geometry raises questions. The so definined computational geometry obviously includes algorithms of geometric constructions since they are also algorithms to solve problems also stated in the terms of geometry. However, the article does not mention such algoithms.

Thus, either the article has to be augmented by mentioning such algorithms or the definition has to be modified.—Preceding unsigned comment added by 47.248.0.45 (talk • contribs)

If it needs to be adjusted you can re-write it so that it is correct and then cite your source. -Barkeep 19:04, 30 May 2007 (UTC)

You missed the beginning of the sentence: "In computer science..." AFAIK Compass and straightedge constructions are mostly of historical and theoretical interest. Just as computations with abacus are not part of computer science, geometric construction with your right hand tied to your back is not studied within computational geometry, simply because of lack modern applications that warrant wasting money on such research. For comparison, geometric problems arising in robot motion are a reputable area of research, including solving 3D assembly puzzles, which I'd say in a way akin to ruler and compass construction puzzles. This topic (I mean geometric assembly amd motion planning problems) is also underdeveloped in wikipedia. `'юзырь mikka 21:22, 30 May 2007 (UTC)

You're wrong. Computer Science is actually the study of all computation, both abstract and mechanical, you can't exclude neither abacus computations nor straightedge constructions.--201.21.181.131 (talk) 01:43, 1 August 2011 (UTC)

Why does the article not cite the source of the current definition ? Where is it from ? Who is the author ? —Preceding unsigned comment added by 47.248.0.45 (talk • contribs)

See "References" section. BTW the preparata-shamos book does mention ruler and compass as prehistory of computational geometry.

Please sign your posts, e.g., by typing 4 tildas (~~~~), which will automatically convert into a sig similar to mine: `'юзырь mikka 21:22, 30 May 2007 (UTC)

The definition should be irrespective of whether it is in computer science, or on Earth, or on the Moon or elsewhere. Also the definition should be irrespective of whether it is possible to get money for such research or not. What you say amounts to the following: Computational geometry is a study of such algorithms to solve problems stated in the terms of geometry, which can be performed by contemporary digital computers AND for which one can get financial support. Right ?

But then we have the following problem: none of algorithms of computational geometry can be performed by contemporary digital computers. All these algorithms assume absolute precision of computation. As soon as the finite precision is taken into account, all the algorithms fall apart. They do not guarantee obtaining the desired results or even their approximations.

Thus, the definition should be further specified as follows: computational geometry is a study of such algorithms to solve problems stated in the terms of geometry, which can be performed by non-existing idealistic digital computer with infinite precision of computation AND for which one can get money. Right ?

47.248.0.45 13:35, 31 May 2007 (UTC)

First of all, please don't put your words in my mouth. I explained a possible reasoning under the current definition and about scope of the article, not gave you a yet another definition.

Now, about your comments. Please be advised that definitions of a very large number of terms do depend on "whether it is in computer science, or on Earth, or on the Moon". You may start from "bug" article. In your case you have some reason, I admit, because I am not aware of significant usage of the term "computational geometry" beyund comp sci. At the same time I fail to see the problem here. The definition merely specifies the domain where the term is used: computer science. At the same time, having a particular context makes it unnecessary t write longer explanations.

Finally, the definition in wikipedia is not cast in stone. User:Barkeep have already told you, if you find a better definition please bring it in, without much angry talk. If you don't like the definition of computational geometry, I would very much like to see you criticizing of wikipedia's definitions of mathematics or philosophy. The point is, some things simply cannot be defined in a narrow way. In particular, I see no reason why "ruler and compass" cannot be studied by computer science. `'юзырь:mikka 17:50, 31 May 2007 (UTC)

My point was to show that computational geometry has to study any geometric algorithms regardless of what computers they are intended for - be it "ruler & compass" or "contemporary digital computers" or something else. The reason is that NONE of them are developed for real digital computers but for their unrealistic idealizations which are not better than analog computers or ruler & compass. Why then restrict oneself to one bad model and not to investigate others ? When running on real digital computers the outcome of the algorithms of "computational geometry" may be worse than when analog computers are applied to solving the same geometric problems or even worse than when ruler & compass are employed. For example, convex hull can be constructed with the help of ruler only. And this construction always suceeds unlike algorithms of "computational geometry". The same hold for constructing shortest path, etc.

And such studies into applying other computers to solving geometric problems do exist. But your encyclopedia misses them, whereas it has to reflect all reasonable points of view and not to restrict itself to presenting the views of the dominating school of thoughts.

47.248.0.45 14:11, 1 June 2007 (UTC)

Wiipedia does not "restrict itself" to anything. It is simply that wikipedia is not perfect. It contains what is writen by you and me and John Doe. You are welcome to add more topic. If you cannot write yourself, you may also calmly, without much agitation suggest titles of new articles. It is not area of political debate or interethnic conflicts, and no one is going to fight you here. `'юзырь:mikka 15:12, 1 June 2007 (UTC)

I would suggest you (as the author of the bulk of the article) to add a section on the computational models for geometric algorithms, emphasize that the most of the research was done for a specific model, outline its shortcomings, mention other models proposed and algorithms for them, refer to comparison of the algorithms for different models from the standpoint of the divergency of computation, etc.

Then it will be worth of an encyclopedia and not a compilation from pieces by O'Rourke & Co.

47.248.0.45 16:40, 1 June 2007 (UTC)

I am afraid that you don't understand the nature of Wikipedia. By its core rule wikipedia:Attribution it is a compilation. It is a major difference from classical encycopedias written by renowned experts all by themselves. By no means I am a world famous expert. It just so happens that there is very few CompGeom experts who are willing to waste their time in a project that brings them neither money nor glory. So take it easy on us; we have no "legal obligations" before readership beyond our free will. And BTW, what you see does not consist of pieces from O'Rourke only. (Not that it is a bad book either.) While I do have this book, I didn't take a single piece from it (some others did, I agree).

That said, thank you for your suggestions. I (or someone else) will try to do something in some spare time. As you understand, I cannot do it right now, happily clicking the keyboard. Serious texts require serious thought. `'юзырь:mikka 17:38, 1 June 2007 (UTC)

List of problems

In the list of computational geometry problems, should we add

• Sweep line algorithm?
• Dynamic programming?

What about the problem of calculating the area of a union of N rectangles? It seems to me a very basic geometric problem. Does it have a page in Wikipedia? --Erel Segal (talk) 16:42, 15 December 2010 (UTC)

Kinetic triangulation

There is a whole series of new articles awaiting new article review, with computer science talk page templates. See Category:All unreviewed new articles. For example, Kinetic triangulation.

I would appreciate reviews by an editor who knows this subject and can provide talk page templates with class and importance. The {{Userspace draft|source=ArticleWizard|date=May 2012}} tags should be removed, and of course any tags for problems should be added. --DThomsen8 (talk) 13:09, 9 June 2012 (UTC)