Newsgroups: sci.math, comp.graphics.algorithms
From: Dan Hoey <haoyuep@aol.com>
Date: Mon, 31 Mar 2008 16:19:25 -0400
Subject: Re: Covering rectangles in 2D

James Waldby wrote:
> quasi wrote:
>> So does that mean that you are, for now, withdrawing your previous
>> claim that the problem has an O(n^(3/2)) (or better) resolution?

> No; as I mentioned in a post on 22 Mar, line sweep methods can be
> done in O(n log n) time using a maintained interval binary search
> tree.

The post of 22 Mar uses terminology such as "the newly introduced
corner" which seems to refer to the algorithm you later agreed was
faulty.  Furthermore, the 22 Mar article claims to offer only an
incomplete description and cites lack of time for your unwillingness
to make it complete.  Under such circumstances, I must doubt any claims
of the algorithm's correctness and performance.

Please spare us the graphs of your program's behavior, which suggest
only that you don't know what kind of an answer would be convincing.
A full description of your proposed algorithm, together with at least
a sketch of the proof of its performance and correctness, are what
might repair this sorry state.

Dan