sorting problem

[James Kanze]

Thanks. My deeper problem is that if I define < on the pairs
to mean (a,b) < (c,d) if the interval (a,b) is _strictly_
contained in (c,d). Then the relation is non-reflexive but is
still not a strict weak ordering.

Correct, since the resulting equiv function isn't transitive.
In fact, if the conditions are met, equiv will define an
equivalent relationship. The problem with the ordering you are
concerned with is that it doesn't define a complete ordering,
there are pairs which are not ordered, but which are not
equivalent. (Another way of expressing the requirements, or at
least a condition that follows from the requirements, is that
for any given pair of elements, one must come before the other,
or they are members of the same equivalence class.)

 

[Comp1597]

(e-mail address removed) wrote:
[...]
Hence my next question is: are there sorting algorithms in the STL
that handle partially ordered sets which aren't strictly weakly
ordered?
I don't think there is.
I can't find anything on the web about this, although I
would have thought it was a standard problem.
E.g., a standard problem in this context is topological sorting: embed a
partially ordered set into a totally ordered set so that the partial
order is preserved. As far as I know, the standard library has no
algorithm for that.

[...]
Thanks Kai-Uwe.  I'm looking for something a bit faster than the
topological sort algorithm which is order n^2.

You are searching for an efficient solution. That is commendable. However,
it would be good if we knew what the problem is. From postings elsethread,
I figured that you want to somehow sort intervals according to inclusion.
But that is an ill-defined problem. What does count as sorted? And _why_ do
you want to sort the intervals? Is it to speed up searching for an interval
containing a given point? In that case, maybe it's easier to solve the
underlying problem. Can you clarify?

Best

Kai-Uwe Bux

Kai-Uwe, you hit the nail exactly on the head.
I would like to search for the number of intervals containing a given
point but only to count the number of intervals. Also, this should be
done dynamically. A large number of searches needs to be done so I
don't want to throw away information.

I've searched online quite a lot and this seems to be in the realm of
computational geometry. However, the only web references I can find
are to much harder problems.

Apparently problems where only counting the number of intervals
involved are referred to as count-mode. However, the references I
found on the web are to higher-dimensional cases.

Any help would be greatly appreciated.

 

[Kai-Uwe Bux]

(e-mail address removed) wrote:

[...]

Hence my next question is: are there sorting algorithms in the STL
that handle partially ordered sets which aren't strictly weakly
ordered?

I don't think there is.

I can't find anything on the web about this, although I
would have thought it was a standard problem.

E.g., a standard problem in this context is topological sorting: embed
a partially ordered set into a totally ordered set so that the partial
order is preserved. As far as I know, the standard library has no
algorithm for that. [...]
Thanks Kai-Uwe.  I'm looking for something a bit faster than the
topological sort algorithm which is order n^2.

You are searching for an efficient solution. That is commendable.
However, it would be good if we knew what the problem is. From postings
elsethread, I figured that you want to somehow sort intervals according
to inclusion. But that is an ill-defined problem. What does count as
sorted? And _why_ do you want to sort the intervals? Is it to speed up
searching for an interval containing a given point? In that case, maybe
it's easier to solve the underlying problem. Can you clarify?

Best

Kai-Uwe Bux

Kai-Uwe, you hit the nail exactly on the head.
I would like to search for the number of intervals containing a given
point but only to count the number of intervals. Also, this should be
done dynamically. A large number of searches needs to be done so I
don't want to throw away information.

Ok. Here is what I would try:

1) I will discuss half-open intervals [a,b). The considerations transfer to
other types of intervals.

2) For each interval I = [a,b), there is an associated characteristic
function

f_I (x) = 1 if x in I and 0 otherwise.

Counting the number of intervals containing x can be thought of as computing
the sum

sum_I f_(x)

where I runs through all the intervals in the given collection.

3) Note:

f_I(x) = f_a(x) - f_b(x)

where f_a is the characteristic function of [a,\infty) and f_b(x) is the
characteristic function of [b,\infty). That is

f_y(x) = 1 if y<=x and 0 otherwise.

4) Thus

sum_I f_I(x) = sum_a f_a(x) - sum_b(x)

where a runs through all left-sides of the intervals and b runs through all
the right sides of intervals.

5) To compute

sum_a f_a(x)

you need to count the number of left sides less than or equal to x. This can
be accomplished by sorting the left sides. Similarly, to compute

sum_b f_b(x)

you need to sort the right sides of all intervals.



Example: given

[1,3) [0, 5) [2,4) [1,6) [4,6) [0,3)

and x = 3 You would do:

sort lefts: 0,0,1,1,2,4 count 5 are <=3
sort rights: 3,3,4,5,6,6 count 2 are <=3

Thus 5-2=3 intervals contain 3. Those are:

[0,5) [2,4) [1,6)

I've searched online quite a lot and this seems to be in the realm of
computational geometry. However, the only web references I can find
are to much harder problems.

Well, finding all intervals containing a given point is more tricky


Best

Kai-Uwe Bux