Conference rusure::math

Since the two partial orderings are on different coordinates, it would seem
that you could pick a set of real numbers {a1,b1,c1,...} that are topologically
sorted on < and another set {a2,b2,c2,...} that are topologically sorted on ^,
and the set of points {(a1,a2),(b1,b2),(c1,c2),...} are sorted on both.

This is easy enough that it probably isn't what you had in mind - how am I
misunderstanding the question?

I specified that the objects occupy a lattice, i.e. the coordinates are
integers. I did not make the goals clear, though. What I should have said
was that the x-y coordinates of each object should satisfy the conditions: 

	o All coordinates are non-negative integers

	o No two objects have the same coordinates

	o All the constraints are satisfied

	o All coordinates are minimal within the constraints

Note that there is still considerable latitude in the placement of 
unconstrained objects, w/r/t the order and position in which they may
appear. 

What I need, of course, is an algorithm to do this in two dimensions in
a reasonable span of time and space. As motivation, note that the algorithm 
given by Knuth for one dimension behaves as O(m+n) in time, where m is the
number of objects and n the number of constraints. I think it's also O(m+n)
in space. 

    Was any of this sorting ever contained in Stan's GRAPHER programs?
    

>    Was any of this sorting ever contained in Stan's GRAPHER programs?
    
Yes, although it was not running when I copied the programs. I have the 
one-dimensional algorithm running, but nothing special beyond that.

Lynn Yarbrough

Richie Lary's solution solves the problem, except for:

>	o All coordinates are minimal within the constraints

which is ill-defined, anyway.  Once defined, it'll probably make
this an NP-complete problem, so don't bother.

Why not take Richie's solution, and just 'squish' it?

The condition 

	o All coordinates are minimal within the constraints

falls like the gentle rain out of the Knuth algorithm. I'd like to retain 
that property in a 2-D algorithm.

> Once defined, it'll probably make this an NP-complete problem, so don't
> bother. 

I can't imagine any reasonable algorithm that would behave worse than
O((m+n)^3). I'd like to get one that is O((m+n)*log(m)), at worst, and 
hopefully better.

However, I'm beginning to agree with you about the general method.

Re .0:

Did you intend to discard this solution to "a<b, a^b, b<c, c^a":

	.c
	a.
	.b

In other words, do you want to allow solutions which have distinct points
with some identical coordinates as long as they don't violate the ordering?

Re .3:

See also the "tsort" tool on Unix.

Re .5:

Unfortunately, the "solution" in .1 doesn't explain *how* to "pick"
an ordering for one coordinate which does not violate the constraints
on the other coordinate.  It describes many procedures, from an exhaustive
search by repeatedly sorting on one dimension and checking the other
one for legality, to any sort of incremental process which sorts both
dimensions at the same time.  I think that Richie understands the problem,
he just didn't go far enough with it to actually give someone a hint
of how to implement an algorithm to solve it.

There is a simple, subquadratic(?), solution to "integerizing" a bunch of
pairs of real coordinates.  Sort the pairs on one coordinate, replace that
coordinate with the position in the sorted array and then repeat the
process on the other coordinate.

Also, while you can efficiently take an integer lattice and trivially
squish it by removing all vacant "rows" and "columns", it would not
surprise me if there are sets of constraints which result in different 2-D
topological sorts which have different trivial squishes with different
sizes (product or sum of max row and column).  Can anyone come up with
an example of this?
				/AHM

re .6

>	o All coordinates are minimal within the constraints

Huh?  Given {a<b, a<c}, the following topological ordering may be
produced by Kahn's algorithm: a, b, c.  The coordinate for 'c'
is not minimal.


re .5, .6:

Consider the relations: {a<b,a<c,a<d,a<e,a^b,a^c,a^d,a^e}.
The following minimizes the maximum x-coordinate:

	a .
	. b
	. c
	. d
	. e

And the following minimizes the maximum y-coordinate:

	a . . . .
	. b c d e

Clearly, the maximum x-coordinate and the maximum y-coordinate cannot
be simultaneously minimized, since 5 nodes cannot fit in a 2x2 square.


re .6:

The above example shows a case where simple 'squishing' won't produce a
solution that minimizes the product of the maximum row and column numbers.
Here *is* such a solution, with a product of 9:

	a . .
	. b c
	. d e