From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.comp.tex.context/6145 Path: main.gmane.org!not-for-mail From: Marco Kuhlmann Newsgroups: gmane.comp.tex.context Subject: Re: How powerful is mp? Date: Wed, 14 Nov 2001 20:07:04 +0000 Sender: owner-ntg-context@let.uu.nl Message-ID: <20011114200704.A636@wimsey> References: <20011107123024.A3646@wimsey> <5.1.0.14.1.20011107183011.04289690@server-1> <20011107174952.A1358@wimsey> <20011108093308.7f315d4e.taco@elvenkind.com> NNTP-Posting-Host: coloc-standby.netfonds.no Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1035396691 7909 80.91.224.250 (23 Oct 2002 18:11:31 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 23 Oct 2002 18:11:31 +0000 (UTC) Original-To: ntg-context@ntg.nl In-Reply-To: <20011108093308.7f315d4e.taco@elvenkind.com> Xref: main.gmane.org gmane.comp.tex.context:6145 X-Report-Spam: http://spam.gmane.org/gmane.comp.tex.context:6145 Hi Taco. Thanks for the qobitree recommendation for a stack-based tree-drawing algorithm. qobitree assumes that the trees have a rectangular envelope, yuk... Taco Hoekwater wrote (2001-11-08 (09:33)): > Kennedy's implementation uses quadratic time. With all respect > for the author himself, I think his article is not very > exciting. So what sub-quadratic algorithms are there? > He does indicate that the implementation can be changed to use > linear time, but doesn't actually show the code that would > result from that. That would have been a lot more interesting > that a couple of recursive functional programming procedures > that are all virtually trivial. One could also say: they show how straightforwardly the problem can be formulated in a functional programming language. :-) However, you are right that he should have shown the linear version as well. I actually wonder if there is one; I spent some time but couldn't figure it out. Gibbons has shown a linear bound for binary trees, but for n-ary trees... Marco -- Marco Kuhlmann marco.kuhlmann@gmx.net