A 'Road Coloring' Problem

This is on the July 2003 challenge at the Ponder This column at IBM Research. See here for the statement of the problem.

This problem is stated to be still open. Here we (N. Ramana Rao and self)look at a special case thereof.

1. We look at the special case of Road Coloring where at least one of the cities has an outgoing road ending in the same city. Suppose there are N cities, and Cx be any of the cities which have road to itself. We do the following visualization:

Keep Cx at the center and arrange the other cities in layers around it. First keep those cities which have roads directly leading to Cx to Cx in the first layer around Cx. Call this layer L1. Now keep the cities which have roads directly leading to cities of L1 in the next layer L2. Thus we keep all the cities in layers around Cx.

The coloring:
For every other city C, there is at least one outgoing road leading into the layer just inside of the layer on which C lies. Color this road from C to its next inner layer red. The other outgoing road from C is colored green. If both roads from C lead to the next inner layer, either may be colored red or green. For the central city Cx, the self-reaching loop road should be red.

With this coloring, one has a constant and finite path leading from ANY city to the central city Cx. This sequence of roads to the central city is always of the form of one Green followed by as many Reds as there are layers (an example is given below).

For any specified city C', there exists a fixed path from central city Cx to it (guaranteed in problem statement). So given any destination C', starting at any unknown source C, we can by first taking the constant path to the center and the path from center to C'. The path will be the same for any starting city C and will depend only on destination C'.

Example:

There are 5 cities numbered 1 to 5. arranged in a pentagon and connected clockwise. 1, 2, 4 and 5 have one road each that loops back on itself. 3-5 is another road.

ie, the roads are 1-2, 2-3, 3-4, 4-5, 5-1, 1-1, 2-2, 3-5, 4-4, 5-5

there are two cycles 1-2-3-5 (length 4) and 1-2-3-4-5 (length 5) - the lengths are relatively prime. As far as we can make out, this property is not used in what follows...

We choose 1 as the central city. The next layer has only 5 (since only from 5 is there a direct path to 1) In the next layer there are two cities, 3 and 4 In the outermost layer there is only 2.

By above coloring scheme, 2-3, 3-5, 4-5, 5-1, and 1-1 should be red and the others roads are green.

The seqeunce GRRR takes you to city 1 from any starting city. Once we have a samepath to the central city from anywhere we also have a same path to any required destination from anywhere.

A 'Line Fitting' Problem

This post came out of a discussion with N. Ramana Rao.

Statement of the Problem:
------------------------
Given a distribution of N points in 2D Euclidean plane. Describe the line which minimizes the Sum of the Orthogonal Distances of the given points from itself.

Please note that we consider abs values of the perpendicular distances themselves, NOT their squares. We could call such a line a "min-SOD line" o r perhaps the "spine" of the point distribution. The line need not be unique.

An Extension: If we are to minimize (the SOD plus the minimum length of the line so that it contains the feet of the perpendiculars from all the input points to the min-SOD line) what could be said about a line that achieves it?

Proposed answer to the main part:
--------------------------------

(This is a 'lemma' which we have tried to use to find an efficient algorithm to compute the min-SOD line).

A min-SOD line (spine) has to pass thru at least two of the input points and should be such that on neither half plane it divides the plane into, there should be more than Floor (N/2) points.

Attempted proof of our lemma:
------------------------------

Consider a line which claims to be the spine and which pass thru none of the N input points. First we note that candidate line has to have equal number of the input points on either side ( else we could shift in parallel to itself in one of the two possible directions and achieve a reduction in SOD).

Let this candidate spine be infinitesimally rotated in the plane about ANY point on itself, say P. Now, for any input point Pi the perpendicular
distance from the candidate spine thru P is given by r* sin t where t is the angle made by the line from P to Pi and the candidate spine . When the line rotates infinitesimally by angle dt, the differential change in the perpendicular distance is r* cos t dt.

We note that if the line were to rotate in the opposite direction from what considered above, the differential change in the perpendicular distance of the point Pi from the candidate spine would simply change sign (because then dt -> -dt ).

So for the entire set of input points, the overall change in the Sum of Orthogonal Distances will also have opposite signs when the candidate spine is rotated in the two possible directions.

This proves that if SOD increases in one direction overall, it necessarily decreases in the other direction - it cannot increase in both directions => the position of the candidate spine is not a minimum for the SOD. However if the candidate line passes thru one of the input points, for that point the perpendicular distance increases in both directions of rotation and then the line COULD BE be one for which the SOD is a minimum.

Special case:
------------
The SOD could be unchanged for both infinitesimal rotations (for example if the input points are arranged along two parallel lines in equal numbers and the candidate spine is parallel to both these lines and equidistant from both). Then we note that this property of unchanging SOD holds only locally and gets lost the moment the we disturb the symmetry of the distribution of the input points about the candidate spine by an infinitesimal rotation of the candidate spine. This always seems to be the case as long as the input points are a discrete set.

Thus we see that the candidate spine has to pass thru at least one input point. We now repeat the above argument with this input point as the center of rotation for the candidate spine; we see that the candidate line has to pass thru one more input point.

We thus conclude that the spine passes thru at least two input points and neither side it has more than floor (N/2) points.

Remarks on computing the spine:
------------------------------
For input points in general position, the spine is one of the Halving lines. So in order to computationally determine the spine for a given point set, we could try to find all the halving lines and compare the Sum of Orthogonal Distances (SOD) of the input points from each halving line.

From the work of Tamal Dey and others on the 'k-set problem', the number of halving lines for N points could be as high as N^4/3. Finding them all could take O(log N) time per halving line using dynamic convex hull data structures. Finding the SOD for one halving line and to recalculate it for each successive halving line could take only constant time per iteration. Thus we could have approximately an O(N^4/3 * log N) algorithm to find the spine. We are grateful to Prof. David Eppstein (UC -Irvine) for pointing out these details to us.

We are not aware of better complexity results for this problem. We also do not know if this problem has been explored before.


The extension:
---------
If we are to minimize {the SOD plus the minimum length of the spine so that it just contains the feet of the perpendiculars from all the input points to the min-SOD line} , the spine again appears to satisfy the above property - it passes thru at least two input points and has <= floor(N/2) points on either side. the same arguments appear to hold.

However, the line that minizes only the SOD and the line minimizing {SOD + 'spine length'} need not be the same. For example, if there are 3 input points at the vertices of an isosceles right triangle, the min-SOD line is the hypotenuse but if we are to minimize the SOD + spine length, we choose either of the two equal sides of the triangle as the spine.

Additional Remark:
------------------

It would seem that the lemma could be improved to at most Floor( (N-1)/2) points on each side of the line. This makes a difference when N is even.

Suppose N is even and we have a line L passing through at least 2 points, with exactly N/2 points on one side. Shift L parallel to itself towards the N/2 points (which does not change the SOD), so it is not touching any points. Suppose L is now the x-axis. Rotate it through theta around the origin.

(Remark: because there are exactly N/2 points on each side, it doesn't matter which point we choose as pivot.)

If there were N/2 points (x_i,y_i) above the axis and N/2 points (z_j, - w_j) below the axis (notice y_i and w_j are all positive), then the SOD (as a function of theta) is ( sum y_i + sum w_j) (cos theta) + ( - sum x_i + sum z_j) (sin theta). The second derivative at theta=0 is ( - sum y_i - sum w_j ) which is negative, so a small rotation in one direction or the other will decrease SOD. So we did not have the minimum. Conclusion: at most Floor((N-1)/2) points on each side of the line.

Note:
-----
For a distribution of points in Euclidean 3D, the min-SOD line NEED NOT pass thru any of the points.

Packing Circles - Questions Galore!

The prime inspiration for this post is 'Erich's Packing Center'. What I have here is a long list of doubts based on the interesting facts given there on the specific problem of packing circles in squares - for a given number N, finding the smallest square which will hold exactly N unit circles. For several examples please see here .

1. It appears that one needs to solve each instance of the problem (each instance given by a certain specified number of circles to be packed in a least square) separately. Are there general rules for characterizing packings like: (i) For what numbers could we always manage with a simple parallelogram lattice of circles (as in the case of 16, 18 and 20 circles for instance) ? (ii) For what numbers will there be one or more 'loose circles' in the packing (circles which can move a finite distance about its position in the packing without violating the square) (7, 11, 17, 21 etc..) ?

Remark: It appears that there are no such rules. Obviously some numbers work well for this 18=4+3+4+3+4 and 20=4+4+4+4+4. But you don't know ahead of time that this translates into an optimal packing.

2. If we allow only simple parallelogram lattices of circles (with one circle per 'unit cell') to be used while packing circles in squares, could we have a general method to find the minimal square given the number of circles to be packed? This becomes relevant if we are automating the packing and can only handle simple lattice arrangements of the circles.

Remark: The hex packing is a lot better than the diamond packing, so for large N this won't be as good - it would be better to place the square over a hex lattice and trap as many circles as possible.

3. If we allow only simple parallelogram lattices but allow the container to be a rectangle with (i) minimum area or (ii) minimum perimeter, do we have a single general algorithm for any number of circles to be packed?

Remark: It appears this is unexplored territory.

4. And if we allow the container to be other than a square, can the 'loose circles' /non-lattice arrangements be always avoided for some specific type of container? Even in the 'Circles in Circles' page at the 'Packing Center', loose circles are seen for some numbers.

Remark: "thin" enough containers won't have this problem, But it is hard to see any shape that won't have this problem when scaled up large enough.

5. It is possible that there is a connection between selections of N circles from a fixed lattice to polyominoes with N squares - the number of different N-ominoes is exponential. The number of candidate circle arrangements perhaps is probably exponential as well.

Maybe we could have ways to filter down the number of candidate selections of circles to a polynomial in N - perhaps by eliminating circle selections corresponding to long 'polyominoes' if one is looking for the smallest square.

Remark: One needs to find a good way to prune the tree of polyominoes to only consider ones that are fat instead of skinny. Perhaps a more general idea of convexity, while making sure the width and height don't differ by 2 or more..


6. I would also like to know if there are any problems in this area which are known to be NP-complete. Finding the minimal square for a given number of circles seems to be far more complex than NP-complete since one cannot choose from a discrete set of options.


8. Here is an apparently simpler problem: Given a known and fixed parallelogram lattice of circles and a number N. Find the minimal area/ perimeter rectangle (or square) that can be placed on the lattice so that it 'traps' N circles fully within it. Does this or some other variant of the main packing problem enable a reduction of the problem to choosing from a discrete set of candidates?

Remark: One needs to see how to reduce the problem to finitely many cases.

Starting Up...

Hello World!

This blog is a spinoff from my 'catch all' collection of personal stuff, 'Anamika' . Here I will try to post as regularly as possible on matters geometric, computational etc..

This initial post is a 'recap'. Let me form here, a 'bucket' of pointers to some selected posts made at Anamika over the last year.


1. On the 'Change Making' problem

2. A problem on Calibrating Glass Bulbs

3. Solution to the Glass Bulb Problem

4. On Partitioning Polygons

5. A Puzzle on Prisoners and Switches

6. More on the Prisoners and Switches Puzzle

7. An encounter with Sudoku

8. A Pigeon Hole Puzzle

9. Speculations on the Angel Problem

10. 'Atomic' Polygons

11. A 'Conjecture'

12. A Conjecture Debunked

13. Cutting Polygons - contd.