*start*
01985 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@20-Aug-83 11:51:45 PDT
Categories: Tracings
Date: 20 Aug 83 11:51:45 PDT
From: Ramshaw.pa
Subject: Eureka!  I've found it!  (Perhaps!)
To: Guibas, Stolfi
cc: Ramshaw

I think that I have figured out the real product rule!  Of course, I've thought that before and been wrong, so don't get too excited.  At least, I have a rule that works correctly in every example that I have tried so far, including those with full turns of arbitrary multiplicity.

The central idea of this new approach is to add in one more kind of thing when computing products in addition to everything that we used to be throwing in.  In particular, suppose that both L and R include a turn at a point p.  Under the old rules, these two turns influenced each other as follows:  the L turn contributed to the winding number of L at p, which affected the multiplicity with which the R was included;  and vice versa.  Under my new rules, this continues to happen as before.  But in addition, I propose that the two turns also have a direct impact on each other:  they cause us to add a turn corresponding to their intersection with multiplicity the negative of the product of their multiplicities.  Wierd, eh?  I never would have guessed it, and maybe it's all wrong.  But it does solve an awful lot of problems.

Thus, my proposed rules for product:

i) Add each turn or move of L as often as it is wound by R;

ii) Add each turn or move of R as often as it is wound by L;

iii) Add patching turns:  for each pair of states x, y with pos(x)=pos(y) and
		angle(x)<angle(y)<angle(x)+pi,
add the turn from x to y with multiplicity one-half of the quantity:
		m+(L,x)*m-(R,y) + m-(L,x)*m+(R,y) + m+(R,x)*m-(L,y) + m-(R,x)*m+(L,y).

iv) Add new funny turns:  for a left turn in L with multiplicity tL and a coincident left turn in R with multiplicity tR, add the intersection of the two turns to the product with multiplicity
		-tL*tR.

Try it, you'll like it.

Lyle


*start*
01197 00094 US 
gvMsgID: Guibas.pa $ 3#14@20-Aug-83 18:40:18 PDT
Categories: Tracings
Date: 20 Aug 83 18:40:18 PDT
From: Guibas.pa
Subject: Re: Eureka!  I've found it!  (Perhaps!)
In-reply-to: "Ramshaw's message of 20 Aug 83 11:51:45 PDT"
To: Ramshaw
cc: Guibas, Stolfi

Lyle:

I have not yet had the chance to play with your rule extensively, but stylistically (I think) it would be preferable to have one that is expressed either (1) purely in terms of moves and turns giving rise to other moves and turns, or (2) purely in terms of pairs of states giving rise to other states. Since product requires the introduction of patching turns, a rule of style (1) can only work if all moves of L and R are decomposed at all common points of L and R. A rule of style (2) would be closer to a fiber product definition and probably has to have embedded in it our winding number conventions. In particular, cases (i) and (ii) of your rule should then become consequences. Case (iii) is already essentially in a (state,state) => state form, and case (iv) can be captured by saying that two coincident turning states of L and R give rise to the same turning state in LR with coefficient -1.

	Leo

 
*start*
00771 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@28-Aug-83  0:16:06 PDT
Categories: Tracings
Date: 28 Aug 83  0:16:06 PDT
From: Ramshaw.pa
Subject: minor twiddle to Leo's product formula
To: Guibas, Stolfi
cc: Ramshaw

Leo and Jorge,

I worked on proving the relation between winding number of the product and product of the winding numbers this evening.  It turns out that, with the addition of one more term to Leo's formula, we arrive at a formula that always holds, even if the two tracings being multiplied include opposite states.  The additional term didn't show up in Leo's analysis because it is only nonzero when the two factors do include opposite moves.  The complete formula is on my whiteboard in brown.  I will try and TeX out the proof tomorrow,

Lyle

*start*
00862 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@26-Sep-83 13:18:01 PDT
Categories: Tracings
Date: 26 Sep 83 13:18:01 PDT
From: Ramshaw.pa
Subject: tracings:  an embarassing admission
To: Stolfi, Guibas
Cc: Ramshaw

I am starting to rewrite my tracings proofs to handle the piecewise real analytic case, instead of the piecewise linear case (all in the plane, though;  no higher dimensions yet).  I have finished the proof of balance for convolution, and I'm working on the proof of integrality for convolution.  In the process, I discovered an embarassing thing:  my polygonal proof is wrong!!  On page 2 of my pre-Labor Day notes, near the end of the page, I claim "the third sum simplifies by algebra to . . .";  but it doesn't.  I shall patch the polygonal version first, then return to extending the arguments to the piecewise real analytic case,

Lyle


*start*
00628 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@26-Sep-83 14:53:49 PDT
Categories: Tracings
Date: 26 Sep 83 14:53:49 PDT
From: Ramshaw.pa
Subject: proof state
To: Guibas, Stolfi
Cc: Ramshaw

The correct proof of integrality of the convolution ends up looking a lot more like the last part of the proof of the convolution theorem.  For details if you're curious, look at
	/Maxc/Ramshaw/Tracings.press.
For the current state of my proofs in the piecewise real analytic case (only balance and integrality of convolution are done so far, and notations are still subject to change) see
	/Maxc/Ramshaw/SmoothTracings.press.

Lyle

*start*
03020 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@28-Sep-83 16:22:23 PDT
Categories: Tracings
Date: 28 Sep 83 16:22:23 PDT
From: Ramshaw.pa
Subject: here is my message to Andy Odlyzko
To: Stolfi
Cc: 

--------------------------------------
Date: 28 Sep 83 15:37:26 PDT
From: Ramshaw.pa
Subject: ordering analytic curves
To: research!rabbit!amo@Berkeley.ARPA
Cc: Greene, Guibas, Ramshaw

Andy,

If f(x) and g(x) are real analytic functions defined in a neighborhood of x=0, we can order f and g unambiguously based upon their values just to the right of x=0, that is, for all sufficiently small positive values of x.  If f(0)>g(0), then f must actually exceed g on a neighborhood;  if f(0)=g(0) but f'(0)>g'(0), then f must exceed g on a neighborhood;  and so on.  This ordering relation of "exceeding for small positive x" corresponds to lexicographic order on the coefficients of the power series.

In trying to extend Leo, Jorge, and my stuff on kinetic geometry, I have run across the following parametric variant of the above problem;  you can probably solve it in your sleep.

Suppose that, instead of analytic functions, we have analytic curves in the plane:  x(t) and y(t) are real analytic functions of t for t in [0,1].  Even though we are dealing with parametric curves, we are not interested in the details of the parametrization.  Therefore, if two curves can be made equal on a neighborhood of 0 by some reparametrization, we shall consider them to be the same curve.  (I'm really dealing with the germs of curves, I guess.)  Let us rule out the curves that don't move at all, that is, where both the functions x(t) and y(t) are constant functions.  On the other hand, we shall allow the first few derivatives of both x(t) and y(t) to be simultaneously zero.  For example, the standard cusp with x(t)=t^2 and y(t)=t^3 is a perfectly legitimate curve leaving the origin.

Consider two curves that leave the origin.  Their slopes at t=0 are well-defined, because we have ruled out the constant curves.  If their slopes at t=0 aren't equal, that tells us right away what their relative locations are near the origin.  But suppose that their slopes at t=0 are both zero;  in fact, suppose that they both leave the origin tangent to the positive x-axis.  This means that each curve will determine y as a function of x for all sufficiently small positive x, although this functional relationship won't necessarily be real analytic.

My question is whether or not such curves can be ordered by their behavior near 0 in the same way that analytic functions can be.  Assuming that two curves aren't coincident, will one of them always be above the other throughout some neighborhood of the origin?  The only alternative that I can see is that the two curves would cross each other infinitely often in every neighborhood of the origin, and I doubt that analytic curves could do such a thing.  On the other hand, I don't see a proof right off that it couldn't happen.

Lyle  

--------------------------------------

*start*
00613 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@29-Sep-83 15:13:58 PDT
Categories: Tracings
Date: 29 Sep 83 15:13:58 PDT
From: Ramshaw.pa
Subject: SmoothTracings.tex, .press
To: Guibas, Stolfi
Cc: Ramshaw

The latest version of SmoothTracings.press on my Maxc directory has the formulas describing the local behavior of winding numbers, defines the product, and shows that products are always balanced tracings.  The notations and proofs can probably be cleaned up a lot;  but, for now, I am going to plunge on and see if I can get through generalizing the rest of the proofs in my write-up instead,  

Lyle


*start*
00841 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@29-Sep-83 17:13:50 PDT
Categories: Tracings
Date: 29 Sep 83 17:13:50 PDT
From: Ramshaw.pa
Subject: Whoops:  another bug discovered
To: Guibas, Stolfi
Cc: Ramshaw

I'm now working on the integrality of product.  Once again, the ``proof'' that I gave in the polygonal case is wrong, so I shall have to fix it before generalizing it.  In particular, I claimed that the multiplicities of the moving states in the product were ``clearly'' integers, since no divisions by two were involved in the formula for them.  BUT:  the winding numbers involved may very well be half-integral instead of integral;  this case arises, for example, when you multiply a tracing times itself.  I need to prove that the two half-integers involved when A winds B and B winds A always sum to an integer,

Lyle
 
  
*start*
00314 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@30-Sep-83 13:45:35 PDT
Categories: Tracings
Date: 30 Sep 83 13:45:35 PDT
From: Ramshaw.pa
Subject: status of tracings
To: Guibas, Stolfi
Cc: Ramshaw

Bug repaired;  SmoothTracings.press now proves balance and integrality for both convolution and product.

Lyle


*start*
01450 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@ 2-Oct-83 11:57:06 PDT
Categories: Tracings
Date:  2 Oct 83 11:57:06 PDT
From: Ramshaw.pa
Subject: PS to: ordering analytic curves
To: research!rabbit!amo@Berkeley.ARPA
Cc: Stolfi, Greene, Guibas, GNelson, Ramshaw

Andy, the result that I was asking about would be an easy consequence of the following Lemma, which I suspect to be true.

Lemma.  Let x(t) and y(t) be real analytic functions of t in a neighborhood of t=0.  Suppose that x(0)=0 but that x is not identically zero;  in particular, assume that the power series of x(t) at t=0 takes the form
	x(t) = c*t^k + d*t^(k+1) + . . .
for some positive integer k and positive real constant c.  Since we are assuming that c>0, we have x(t)>0 for t sufficiently small and positive.  Thus, for sufficiently small positive x, we can think of y as a function of x.  Now, y's dependence upon x will not in general be analytic.  The claim of this lemma is that y will always be an analytic function of x^(1/k).

Once this Lemma is proven, the result in the earlier message follows by a simple trick:  if one of the y's is analytic as a function of x^(1/m) and the other is analytic as a function of x^(1/n), they will both be analytic as functions of x^(1/(m*n)).

As far as proving the Lemma goes, it is pretty easy to compute the power series of y as a function of x^(1/k).  The question of uniform convergence remains to be tackled, however.

Lyle


*start*
00348 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@ 3-Oct-83 17:02:31 PDT
Categories: Tracings
Date:  3 Oct 83 17:02:31 PDT
From: Ramshaw.pa
Subject: tracings
To: Guibas, Stolfi
Cc: Ramshaw

Latest version of SmoothTracings includes proof of the formula for the winding number of a product tracing.  Convolution theorem is all that's left,

Lyle


*start*
01355 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@22-Oct-83 16:57:52 PDT
Categories: Tracings
Date: 22 Oct 83 16:57:52 PDT
From: Ramshaw.pa
Subject: Re: new theory of planar curves
In-reply-to: "Newlin's message of 18 Oct 83 10:49:15 PDT (Tuesday)"
To: Newlin
Cc: Stolfi, Guibas, Ramshaw, Mallgren

Jack, I sent you a copy of the paper on the subject that Leo, Jorge, and I wrote for FOCS.  It presents the correct definitions and proofs for the polygonal case, although the presentation is somewhat terse at times.  I have extended the definitions to handle piecewise real analytic curves, which I now believe to be the "right" framework (for curves in the plane anyway;  surfaces in three-space are less clear to me), continuing to build on Jorge's extended definition of winding number as discussed in Dealer.  And I have worked through some of the proofs for curves as well, but not yet the most important one:  the proof of the Convolution Theorem.  And right at the moment, I'm taking a break from trying to get that proof to work on TeX82 (translated from Pascal to Cedar, so that we can stop using the TeX on MAXC).  

Why don't you glance at the paper, and see if it makes sense.  Then call me sometime, and we'll consider what facets of the theory you or the SDD Advanced Development friday lunch meeting might like to hear more about,

Lyle


*start*
00932 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@ 1-Nov-83 16:50:51 PST
Categories: Tracings
Date:  1 Nov 83 16:50:51 PST
From: Ramshaw.pa
Subject: So, you like geometry?
To: James.Saxe@CMU-CS-A, Guibas, Greene, Stolfi, GNelson, Plass
Cc: Swinehart, Ramshaw

Let k>=2 be an integer.  Construct an equilateral triangle of side length (k^2-1).  Choose one side of this triangle to be the base, and divide it into two parts of lengths (k^2-2*k) and (2*k-1).  Prove that the distance from the point of division on the base to the opposite vertex is the INTEGRAL quantity (k^2-k+1).  

This nice fact was discovered by Paul Mielke of Wabash College (or University?), who used it as the basis of a pretty picture.  Various pretty pictures can be drawn taking advantage of the fact that (k^2-2*k), which is the length of one part of the base, also happens to be ((k-1)^2-1), which is the side length of the figure with k_(k-1).

Lyle
 

*start*
01020 00094 US 
gvMsgID: stolfi.pa $ 3#14@ 1-Nov-83 18:37:15 PST
Categories: Tracings
Date:  1-Nov-83 18:37:15 PST
From: stolfi.pa
Subject: Geometry book - Ch.8
To: Guibas
cc:  stolfi

Leo, 

[ivy]<Stolfi>GB>GBb08.tex contains what I got so far on chapter 8 (minus the "intermezzo" on geometrical primitives and the quadratic mapping).

Sections 1 and 2, and section 3 up to algorithm 7, are reasonably consistent (I hope). Section 2A and everyting after algorithm 7 is still raw junk copied from the STOC paper and from older versions of this chapter, and is there mostly as a placeholder. 

Could you help me sort this mess out? If I go on writing as I have done so far, I am afraid the chapter will not be finished before 1994, and will be a few thousand pages long. Please, chop it down!!! 

GBb08.tex \inputs the following TEX macros:

BasicMacros.tex TR10Fonts.tex GBMacros.tex GeoMacros.tex KineMacros.tex QuadMacros.tex TR10GBWideFormat.tex

all in the directory [ivy]<Stolfi>TEX>.

thanks a lot,

jorge
*start*
06578 00095 US 
gvMsgID: Ramshaw.pa $ 3#14@ 2-Nov-83  9:04:43 PST
Categories: Tracings
Date:  2 Nov 83  9:04:43 PST
From: Ramshaw.pa
Subject: FYI:  Jim Saxe's response to my message about Mielke
To: Guibas, Greene, Stolfi, GNelson, Plass, Swinehart
Cc: Ramshaw


--------------------------------------
Received: from CMU-CS-A.ARPA by PARC-MAXC.ARPA;  2 NOV 83 00:01:36 PST
Received: from [128.2.254.192] by CMU-CS-PT with CMUFTP;  2 Nov 83 02:21:15 EST
Date: 2 Nov 83 02:13 EST
From: James.Saxe@CMU-CS-A.ARPA (C410JS30)
To: Ramshaw.pa
Subject: So, you like geoXXX number theory?
CC: James.Saxe@CMU-CS-A.ARPA
In-Reply-To: "Ramshaw.pa@PARC-MAXC.ARPA's message of 1 Nov 83 19:50-EST"
Message-Id: <02Nov83.021306.JS30@CMU-CS-A>

Let x and y be any non-zero integers, with x <> -y.Take
    a = |x^2-3(y^2)+2xy|,
    b = |4xy|, and
    c = |x^2+3(y^2)|.
Then the angle C subtended by side c in a triangle with sides a, b,
and c is either 60 degrees or 120 degrees.  To see this, note first
the conditions on x and y guarantee that a, b, and c are strictly
positive.  Then, by the second law of cosines, we have
    c^2 = a^2 + b^2 - 2ab(cos C),
or equivalently
    cos C = (a^2+b^2-c^2)/2ab
          = [(xxxx+4xxxy-2xxyy-12xyyy+9yyyy)+(16xxyy)-(xxxx+6xxyy+9yyyy)]/2ab
          = (4xxxy+8xxyy-12xyyy)/|2(xx+2xy-3yy)(4xy)|
          = +-1/2.
If we take x = 2k-1 and y = 1, we get
    a = (4k^2-4k+1) + (4k-2) - 3 = 4k^2-4,
    b = 8k - 4, and
    c = (4k^2-4k+1) + 3 = 4k^2-4k+4,
or equivalently,
    a/4 = k^2-1,
    b/4 = 2k-1, and
    c/4 = k^2-k+1.
This last is the family of values found by Mielke.

Now what's really going on here?  Consider a triangle ABC, with sides
a, b, and c opposite vertices A, B, and C, respectively.  We want to find
integer values for the lengths of a, b, and c such that angle C will be
60 degrees.  Drop a perpendicular from A intersecting line BC at point D.
Then we have
    sin B = BD/c = (a - b/2)/c       [a rational number], and
    cos B = AD/c = b(3^0.5)/2c       [a rational multiple of 3^0.5].
So the problem is to identify all angles B such that sin B is rational
and cos B is a rational multiple of the square root of 3, or equivalently,
to find all integer solutions of the equation p^2 + 3q^2 = r^2.  I can
show that (multiples) of all such solutions are found by taking
    p = x^2 - 3y^2,
    q = 2xy, and
    r = x^2 + 3y^2,
for appropriate x and y.  It is easy to verify that any integer values
for x and y give valid values for p, q, and r.  To show that (some
multiple of) any triplet (p,q,r) such that p^2 + 3q^2 = r^2 can be
generated by some pair (x,y), just make x/y = 3q/(r-p).

At this point, it would seem that we know all there is to know about
the class of angles (let's call them Mielke angles for want of a better
term) whose cosines are rational and whose sines are rational multiples
of the square root of 3.  Not so.  Using the trigonometric formulas for
sin(A+B) and cos(A+B), it is easy to show that the Mielke angles form
a group under addition.  What is the structure of this group?

As a starting point, we can consider what is known about the related
group of Pythagorean angles--that is, those angles having rational
sine and rational cosine.  The Pythagorean angles correspond to
solutions of the Diophantine equation p^2+q^2=r^2, and (multiples of)
all Pythagorean triples can be found by taking
    p = x^2-y^2,
    q = 2xy, and
    r = x^2+y^2,
for appropriate (x,y).  For any prime number r which is equivalent to
1 mod 4, there is a unique (up to interchanging x and y) solution in
integers to the equation x^2+y^2 = r^2.  This solution gives a unique
(up to interchanging p and q) nontrivial Pythagorean triple (p,q,r)
for each prime r equivalent to 1 mod 4.  Examples are (3,4,5) [based
on 2^2+1^2=5], (5,12,13) [based on (3^2+2^2=13)], (15,8,17) [based on
4^2+1^2=17], etc.  These Pythagorean angles, together with the right
angle, generate the entire group of Pythagorean angles.  Moreover,
each Pythagorean angle is uniquely generated, except for the
possibility of adding in any multiple of four extra right angles.
For any sum of these generators, the r (hypotenuse) of the sum (when
reduced to lowest terms by dividing out all common factors of p, q,
and r) is equal to the product of the hypotenuses of the generators.
For example, by adding the 0, 1, or -1 instances each of the angles
in the (3,4,5) and (5,12,13) triangles [i.e., arcsin 3/5 and
arcsin 5/13], and normalizing to the first quadrant, we obtain all
nine solutions to p^2+q^2 = 65^2 (p>=0,q>0):
   p=0,  q=65         p=39, q=52         p=52, q=39
   p=25, q=60         p=33, q=56         p=63, q=16
   p=60, q=25         p=16, q=63         p=56, q=33
Similarly, multiplying arcsin 3/5 by 0,1,2,-1, or -2 gives all five
solutions to p^2+q^2 = 25^2 (p>=0,q>0):
    p=0,q=25    p=15,q=20    p=24,q=7    p=20,q=15    q=7,p=24
These results about the Pythagorean group are based on a formula due
to Jacobi for counting the number of ways (zero or more) in which any
integer is expressible as the sum of two squares.  I don't know the
details of the mathematics used to derive this.  The article in the
Encyclopedic Dictionary of Mathematics says "... the equation [EQUATION]
leads to [FORMULA FOR # OF SOLUTIONS].  This result was obtained by
C. G. J. Jacobi (1829) ..."  However, [EQUATION] involves the Dedekind
zeta function, and I don't have my act together well enough to follow
any arguments involving Dedekind zeta functions, nor do I know what
method Jacobi used (presumably it was something else, since Dedekind
was born in 1831).

Getting back to the Mielke group, I am inclined to conjecture on the
basis of analogy to the Pythagorean group that there is some set of
generators such that each element of the Mielke group is uniquely
expressible as a sum of integer multiples of generators (up to
congruence modulo 60 degrees).  I'd be interested in hearing if you
or anyone else can prove (or disprove) this and/or characterize
a set of generators.  Also, is there an interesting generalization
from the Pythagorean and Mielke groups to some infinite family of
related groups, or will attempts at generalization fail for reasons
having to do with the impossibility of tesselating the plane with
pentagons, heptagons, etc.?

				--Jim

P.S.,
	I wouldn't be surprised if someone had already studied this
stuff.  It might be advisable to check the literature before throwing
around the term "Mielke group" in contexts where someone is likely to
start spreading it.
				--Jim

--------------------------------------


*start*
00994 00096 US 
gvMsgID: Ramshaw.pa $ 3#235@13-Nov-83 14:46:52 PST
Categories: Tracings
Date: 13 Nov 83 14:47:00 PST
From: Ramshaw.pa
Subject: n points in the plane, with k to the left of a line
To: Guibas, Greene, Stolfi, Plass
Cc: Ramshaw

Dan reduced the problem to finding an upper bound on the number of transpositions that occur between the k'th and (k+1)st places while the permutation (n, n-1, ..., 2, 1) is sorted with (n\choose 2) transpositions.  Using this reduction, I can prove an O(n^(3/2)) bound.  But I think that the real truth is linear---in particular, (2-1/k)*n for the transposition version, twice that for the points in the plane.

Mike constructed a configuration of 10 points in the plane such that the monostrofic tracing dividing them in the pattern (3, 1, 6) has 30 segments in it.  A rough sketch (of the points without any lines) is in orange on my whiteboard,  

Lyle

�ÊO˜JšÐbsœ˜Jš�œ˜Jš�œ5˜<Jš�œ˜!Jš�œ	˜J˜J˜‘—…—.ƒ*start*
01022 00096 US 
gvMsgID: Ramshaw.pa $ 3#235@15-Nov-83  9:22:52 PST
Categories: Tracings
Date: 15 Nov 83  9:22:55 PST
From: Ramshaw.pa
Subject: transpositions around the middle
To: Guibas, Greene, Stolfi
Cc: Megiddo, Ramshaw

Yesterday, Nimrod claimed that a nonlinear number of transpositions was possible.  Here is an example with n*log(n) that I constructed last night:  Divide the sequence (1, 2, 3, ..., n) into thirds, called A, B, and C.  Our intial state is 
	CR | BR | AR
where the "R" denotes reversed, and "F" shall later denote forward.  Perform the following algorithm:
	CR | BR | AR  ->
	CR | BF | AR  ->
	CR | AR | BF  ->
	CR | AF | BF  ->
	AF | CR | BF  ->
	AF | CF | BF  ->
	AF | BF | CF.
If f(n) is the number of transpositions across the midline, we find that 
	f(n)=3*f(n/3)+3*(n/6),
so f(n)=O(n*log(n)).

I'm pretty sure that this can actually be realized by a set of n points in the plane as well,

Lyle
	

�ÊO˜JšÐbsœ˜Jš�œ˜Jš�œ"˜)Jš�œ˜Jš�œ˜J˜J˜¾—…—JŸ*start*
00742 00095 US 
gvMsgID: Guibas.pa $ 3#183@15-Nov-83 11:43:03 PST
Categories: Tracings
Date: 15 Nov 83 11:42:52 PST
From: Guibas.pa
Subject: Another curious fact
To: Ramshaw, Greene, Stolfi, Megiddo
cc: Guibas

After a conversation with Nimrod the following fact emerged, for which I now have a proof.

In the geometric dual of the original problem one is given n oriented lines in the plane whose orientations are consistent, in the sense that there is some point that is to the left (or the right) of all the lines. If one constructs circuits by replacing each line crossing "X" by "><" in a way consistent with the orientations, then the number of circuits is independent of the arrangement and always equal to ceiling(n/2).

	Leo
*start*
00792 00096 US 
gvMsgID: Ramshaw.pa $ 3#235@19-Nov-83 21:23:04 PST
Categories: Tracings
Date: 19 Nov 83 21:23:02 PST
From: Ramshaw.pa
Subject: status report
To: Yao, Plass, Stone, Greene, Guibas, Stolfi, vanLeunen, MBrown
Cc: Ramshaw

I wasn't around Wednesday through Friday because I came down with this season's stomach flu.  It's a badie---I strongly recommend that you avoid it.  Live healthy, get lots of sleep, and lay in a store of Pepto-Bismol just in case these measures don't suffice.

I may be in for a few hours Monday morning, but then I shall be leaving on a personal trip through Thanksgiving.   Keep the faith;  I may even be back in time to write my performance appraisal.

Lyle


�ÊO˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ>˜@Jš�œ	˜J˜J˜Ï—…—d¹*start*
01793 00096 US 
gvMsgID: stolfi.pa $ 89#132@30-Nov-83 18:20:21 PST
Categories: Tracings
Date: 30 Nov 83 18:20:06 PST
From: stolfi.pa
Subject: Voronoi on a sphere
To: Guibas
Cc: stolfi

Leo: were you aware of the fact below? I (shame, shame) was not, in spite of all our tinkering with the lambda mapping and spherical projections to explain planar Voronoi diagrams...

------------------

Received: from SU-AI.ARPA by PARC-MAXC.ARPA; 29 NOV 83 21:14:32 PST
Date: 29 Nov 83 21:04 PST
From: Ken Clarkson <KLC@SU-AI.ARPA>
Subject: geometry question  
To: stolfi.PA, KLC@SU-AI.ARPA


Hi.  I've run into something I'm sure you know something about.  Can
an analog of the InCircle test be used to compute spherical Voronoi diagrams?
I think that the appropriate InCircle test is even simpler than the one
described in your STOC (FOCS?) paper, but I'm not sure.

Is it really only required of the InCircle test that it test if a point D
is inside the circle of points A,B, and C?

What does it mean for a point to lie to the left of a circle?  Is this a 
duality notion or something?

Any help you can give me would be appreciated... incidentally, the sooner
the better...if you're reading this Tuesday night, could you call me at
497-9558?

thanks,
Ken

Received: from SU-AI.ARPA by PARC-MAXC.ARPA; 30 NOV 83 16:12:22 PST
Date: 30 Nov 83 16:09 PST
From: Ken Clarkson <KLC@SU-AI.ARPA>
Subject: geometry question  
To: stolfi.PA, KLC@SU-AI.ARPA


Ahah!  The "spherical Delauney triagulation" of a set of points on a sphere is
just the 3D convex hull of those points!

-Ken
(I'm pretty sure -- the circumcircle Delauney property and the hull property
coincide)

--------------

jorge
�Êh˜Jš
œ˜Jš
Ïb˜JšÐbsœ˜Jšžœ˜
Jšžœ˜
J˜J˜·
J˜Jš
ÏfÚ˜ÚJš
Ÿ”˜”J˜J˜—…—4¢*start*
00336 00095 US 
gvMsgID: Guibas.pa $ 3#183@30-Nov-83 19:05:39 PST
Categories: Tracings
Date: 30-Nov-83 19:06:21 PST
From: Guibas.pa
Subject: Voronoi on a sphere
To: Stolfi
cc: KLC@SU-AI.ARPA, Guibas

In fact the intersection of the plane supporting a convex hull face with the sphere is the corresponding Delaunay circle.

	L. 
*start*
04665 00096 US 
gvMsgID: stolfi.pa $ 89#132@30-Nov-83 20:12:38 PST
Categories: Tracings
Date: 30 Nov 83 20:12:34 PST
From: stolfi.pa
Subject: Voronoi on a Sphere
To: Ken Clarkson <KLC@SU-AI.ARPA>
Cc: stolfi, Guibas

Well, it seems you found the answer before I even read the question.  Confound me, I hadn't thought much about Voronoi on the sphere (using spherical distance); I guess I expected them to be somewhat more complex than Voronois on Euclidean spaces, as is the case of Voronois using other non-Euclidean metrics. Instead, the former seem to be simpler than the latter. Amazing. (However, I am sure other Voronosophers must have noticed it before).

I knew very well that (Delaunay on the plane) = (Convex hull on the sphere) under stereographic projection, but I failed to notice that the latter was the Delaunay of the spherical problem, too.    
 
As used in our algorithm, the InCircle test indeed has only to test if a point D is inside the circle of points A,B, and C, where ABC is a ccw oriented triangle.  However, we believe the simplest implementation of InCircle (by evaluation of the 4x4 determinant given in our STOC paper) generalizes this to mean "point D is on the left side of the oriented circle ABC". This is the circle passing through the three points and oriented from A to B to C; its left side is its interior (in the usual sense) if ABC is a ccw triangle, and is the exterior if ABC is a cw triangle.

This generalization is necessary for the spherical problem, where the notions of "interior" and "exterior" of a circle become somewhat ambiguous. The left side of the oriented circle ABC then corresponds to that side of the plane pasing through A,B,C from which ABC is seen as a ccw triangle. By the appropriate definitions, this is also the left side of the oriented plane defined by the points ABC. So, InCircle (ABCD) = "D is to the left of the oriented plane ABC" = "ABCD is a positively oriented tetrahedron". The spherical InCircle test is then the same as the planar one, minus the quadratic mapping (or stereographic projection)    

The planar Delaunay condition (ABC is a Delaunay triangle iff no other site is inside the circle ABC) then becomes "ABC is a face of the spherical Delaunay iff no other site is to the left of the oriented plane ABC", which is precisely the condition for ABC to be a face of the convex hull of all sites.

I can even see now a more general principle behind this. Let S be a metric space of dimension 2 (i.e., a surface plus a distance function defined on its points). Define a "circle" on S as a set of the form [ x : dist(x, c) < r ], for some point c in S and some radius r.  Now consider a mapping f, from S into another metric space S' (with some unrelated distance dist'), that maps circles of S into circles of S'.  Then the Delaunay diagram of a set of points P in S is topologically equivalent to the Delaunay diagram of f(P) in S'.

This conclusion is trivial, of course, if f preserves distances (dist'(f(x), f(y))= dist(x,y)) or at least the ordering of distances (dist(x, c) < dist(y,c) implies dist'(f(x), f(c)) < dist'(f(y),f(c))); in this case f also maps a Voronoi diagram on S into a Voronoi diagram on S'. This is for example the case of our quadratic mapping lambda: (x,y) --> (x,y,x2+y2), where dist on the paraboloid z=x2+y2 is the horizontal distance (ignoring the z coordinate).

However, some quite interesting transformations preserve circles without satisfying either of this properties. Among them are the "inversions of three-space around a sphere Z" (map each point p in space to the point p' on the same ray from the center c of Z, at a distance dist(c, p')=1/dist(c,p) ). Any such inversion f maps any sphere S to another sphere S', and circles on S to circles on S', but does not preserve the ordering of distances, and does not map centers into centers.

The stereographic projection h is just a special case of inversion. In fact, it is a degenerate case, since the plane is the only sphere where a circle does not correspond to a planar section. To evaluate InCircle(ABCD) on a sphere we only need to test whether D is on the left side of the plane ABC; to evaluate InCircle(ABCD) on the plane, we have to map it first onto a non-degenerate sphere, or onto our paraboloid.

Well, enough ramblings for now. Thanks for the observation,

jorge

PS: I guess the above also confirms Dr. B. Board Flamer's Law, "the information density of a message is inversely proportional to the square of its length"... 
  
�Ê„˜Jš
œ˜Jš
œ˜JšÐbsœ˜Jš�œ˜!Jš�œ˜J˜J˜½J˜È
Jš
œ¾˜¾Jš
œ�˜�Jš
œ°˜°J˜—J˜ÌJ˜äJ˜¤J˜CJ˜Ÿ
J˜—…—PÚ*start*
02008 00095 US 
gvMsgID: Guibas.pa $ 3#183@ 5-Dec-83  9:38:31 PST
Categories: Tracings
Date:  5-Dec-83  9:38:39 PST
From: Guibas.pa
Subject: Random
To: Stolfi
cc: Guibas

I'm still preoccupied with performance appraisals today. You might want to try and verify the following statements:

Take n points in the plane, no three collinear. Let k be an integer between 0 and n-1. Sweep a line parallel to itself until there are exactly k points to the left of the line, and one on the line (ignore for the moment the case where there could be two). Now rotate the line ccw around that point until another is hit. When this occurs switch the center of rotation to the new point and continue rotating ccw, repeating this process.

Claim 1. The line eventually returns to its original position;

Claim 2. If l is a line having the property described in the above paragraph, then our rotating line will at some point pass through l;

Claim 3. This process defines a monostrofic polygon, in the obvious way: the car goes fwd when the new pivot point is ahead on the line, and bkwd, when it is behind.

Claim 4. The collection of all points of the plane lying to the "n-k" side of all sides of this monostrofic tracing may be empty. This will surely be the case when k > n/2. However, by Helly, this collection will be non-empty when k =< n/3. When the collection is non-empty, its points define a convex polygon. This convex polygon is characterized by the property that any line through each of its points divides the n given points in two groups of which the smallest is at least of size min{k,n-k} and the largest is at most max{k,n-k}.

Claim 5. Considering all k, we get ceiling(n/2) such monostrofic tracings.

Open question: what is the maximum nunber of sides on such a tracing?

-----------------------------

At your convenience, please

1. check with Ed Taft about dumping our files on tape

2. check with Kate about any paperwork you may need to fill out to continue on the payroll in 1984.

	L.


*start*
00532 00095 US 
gvMsgID: Megiddo.PA $ 3#73@10-Dec-83 13:47:40 PST
Categories: Tracings
Date: 10 Dec. 1983 1:40 pm PST (Saturday)
From: Megiddo.PA
Subject: 4-partitioning in the plane
To: Guibas, Greene, Ramshaw, Stolfi, Clarkson, Yao
cc:  Megiddo

(Given  n points find two straight lines that partition them into four equal sets)

I found the way to do it deterministically in linear time. It's (once again!) based
on finding medians in linear time, and can be implemented more efficiently with
random selections.

Nimrod

*start*
03124 00096 US 
gvMsgID: stolfi.pa $ 89#132@13-Dec-83 10:06:28 PST
Categories: Tracings
Date: 13 Dec 83 10:06:14 PST
From: stolfi.pa
Subject: Lines in space
To: Guibas, Ramshaw
Cc: stolfi

I was trying to generalize the theory of the two-sided plane to higher dimensions, and I am having some trouble. I guess I am missing something trivial.

Consider ordinary three-dimensional Euclidean space completed with the "plane at infinity" U, with the convention that a point at infinity in the direction d is the same as the one in the direction -d. The resulting manifold is called (if I am not mistaken) three-dimensional projective space, and is homeomorphic to the "surface" of a four-dimensional sphere in which diametrically opposite points are identified. Denote it by P3.

Consider the set L of all straight lines in this manifold (i.e., all straight lines in ordinary three-space plus the lines on U).  This set is a FOUR-dimensional manifold (do you buy that?).

Question number 1: What is the topology of L?  My easy guess is that it is homeomorphic to  four-dimensional projective space, i.e. P4. However, I have not been able to prove it is not something else, for example P2 x P2.  [In general, the set L[d', d] of all d'-dimensional subspaces of d-dimensional space is a manifold with dimension d'' = (d'-1)(d-d'). Question number 1 then generalizes to: is L[d', d] homeomorphic to Pd'', or to P(d-1) x P(d-d')?]

Question number 2: How should we represent a line in three-space? If L is indeed homeomorphic to P4, it should be possible to characterize a line by FIVE "homogeneous coefficients" <A, B, C, D, E>, such that  <ABCDE> and <A'B'C'D'E'> are the same line iff one is a nonzero multiple of the other. If L is P2 x P2, then there should be a representation using two sets of three coefficients, <ABC | DEF>, with each half determined up to an INDEPENDENT non-zero scalar factor. In either case, the tests for a point being on the line, two lines intersecting, and so forth should be nicely symmetric on all those coefficients.

I found neither. I found a nice, symmetrical representation using SIX coefficients: If a = [xa ya za wa] and b=[xb yb zb wb] are two distinct points on the line (in homogeneous coordinates), then take
      	| xa  ya |
Axy= 	|         |
      	| xb  yb |

      	| xa  za |
Axz= 	|         |
      	| xb  zb |

and similarly for Axw, Ayz, Ayw, Azw.

Then a point p=[xp yp zp wp] is on the line iff

(Ayz xp  - Axz yp + Axy zp)^2 +
(Ayw xp  - Axw yp + Axy wp)^2 +
(Azw xp  - Axw zp + Axz wp)^2 +
(Azw yp  - Ayw zp + Ayz wp)^2 = 0

(Incidentally, the terms within the parenthesis are the coefficients of the equation of the plane abp in homogeneous coordinates.)

 It is easy to see that multiplying all the A## by a nonzero constant gives an equivalent inequality, but cannot quite see how to express the other degree of freedom present in the A##s, and neither recombine them into five equally significant coefficients. Help!.

Thanks, 

jorge  
�Êu˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ˜Jš�œ˜
J˜J˜™
J˜°J˜¿
J˜ÇJ˜íJ˜ÝJ˜²
J˜J˜ƒ
J˜‰J˜—…—ZÕ*start*
01067 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@13-Dec-83 11:29:07 PST
Categories: Tracings
Date: 13 Dec 83 11:29:14 PST
From: Ramshaw.pa
Subject: Re: Lines in space
In-reply-to: "stolfi's message of 13 Dec 83 10:06:14 PST"
To: stolfi
Cc: Guibas, Ramshaw

Quick comments:  

1)  In the non-projective case, the manifolds formed by all k-dimensional subspaces of an n-dimensional space is called a Grassman manifold.  Grassman manifolds are pretty common example cases in differential geometry books.  My sense is that they are a pretty rich class of manifolds, topologically;  they aren't all homeomorphic to vector spaces, or something like that.  I would guess that the same is true in the projective case as well.  

2)  My first guess would be that the other degree of freedom comes from the fact that not all 6-tuples of numbers can occur as <Axy, Axz, Ayz, Axw, Ayw, Azw>;  there is probably some polynomial identity on these six values that is nonzero.  

Lyle


�ÊX˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ.˜9Jš�œ˜
Jš�œ˜J˜J˜É—…—pÎ*start*
01979 00096 US 
gvMsgID: stolfi.pa $ 89#132@14-Dec-83  7:39:17 PST
Categories: Tracings
Date: 14 Dec 83  7:38:54 PST
From: stolfi.pa
Subject: Re: Lines in space
In-reply-to: "Ramshaw's message of 13 Dec 83 11:29:14 PST"
To: Ramshaw
Cc: stolfi, Guibas

Thanks for the hint. I have looked up Grassmann manifolds on the EDM.  I have not decyphered everything yet, but it seems they are really what I am after.

The EDM defines a Grassmann manifold Gn,k as the set of all LINEAR k-dimensional subspaces of R^n.  Now there is a one-to-one correspondence between those subspaces and the (k-1)-dimensional PROJECTIVE (~affine) subspaces of (n-1)-dimensional projective space, which is what I was after.

Actually, the thing I REALLY was after is what they call the ORIENTED Grassmann manifold G'n,k, the set of all oriented k-dim. linear subspaces of R^n, which are in one-to-one correspondence with the oriented (k-1)-dim. affine subspaces of (n-1)-dim. two-sided space. In particular, the set of oriented lines in two-sided three-space is G'4,2.

The EDM says that G'n,k is homeomorphic to SO(n)/SO(k) x SO(n-k), where SO(k) is the group of (orientation-preserving) rotations in R^k. It also says that Gn,1 is equivalent to P(n-1), and that G'n,1 is equivalent to the (n-1)-dimensional sphere. It says nothing about general G'n,ks, so I must assume they are original beasts indeed. Therefore, there is no homogeneous five-parameter representation for lines in space (nor a doubly homogeneous three-plus-three-parameter one).

I will try your suggestion and look for identities involving the Aij.  My next guess is that there is some "pseudo-homogeneous" representation, say using six coefficients in a 3 by 2 array, determined up to multiplication by an orthogonal 2 by 2 matrix with positive determinant. Or something like this. 

Thanks. See you,

jorge 


�Ên˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ/˜:Jš�œ	˜Jš�œ˜J˜J˜›
J˜ J˜ØJ˜ÞJ˜±J˜J˜—…—è\*start*
00386 00095 US 
gvMsgID: Megiddo.PA $ 3#73@14-Dec-83  9:05:54 PST
Categories: Tracings
Date: 14 Dec. 1983 9:05 am PST (Wednesday)
From: Megiddo.PA
Subject: Re: 4-partitioning in the plane
To: Guibas, Yao 
cc: Greene, Ramshaw, Stolfi, Clarkson, Megiddo 

Well. I indeed know how to do it in linear-time.  Please stop by and I'll show
you if you are interested.

Nimrod
Message

*start*
02336 00095 US 
gvMsgID: Guibas.pa $ 3#183@14-Dec-83 12:55:40 PST
Categories: Tracings
Date: 14-Dec-83 12:55:24 PST
From: Guibas.pa
Subject: Re: Lines in space, 2-nd message
To: Stolfi
cc: Ramshaw, Guibas

You are right. In solid analytic geometry the most common representation of a line is via a sixtuplet of numbers (p,q,r,a,b,c), where you can think of (p,q,r) as a point on the line, and of (a,b,c) as a point (other than the origin) on a line through the origin and parallel to the given one. When a, b, and c are normalized so that a^2+b^2+c^2=1, they are called the directional cosines of the line.

There are two families of linear transformations on (p,q,r,a,b,c) that leave the line invariant. The first is (a',b',c') _ (lambda a, lambda b, lambda c) for some non-zero constant lambda. The second is (p',q',r') _ (p + mu a, q + mu b, r + mu c), for some constant mu. These are conveniently expressed by viewing the line as a 2X3 matrix [p,q,r//a,b,c] and asserting that the line is invariant by left multiplication with non-singular matrices of the form [1,mu//0,lambda]. Of course you want to restrict lambda to be positive for the oriented case.

Some other useful facts about this representation are (we did have lots of geometry in high school!):

Condition for lines l and l' to be coplanar is

	detrminant[a,a',p-p'//b,b',q-q'//c,c',r-r'] = 0.
	
Condition for lines l and l' to be perpendicular is

	aa' + bb' + cc' = 0.
	
Distance from point (x,y,z) to line l is d, where

	d^2 = (X^2+Y^2+Z^2)/(a^2+b^2+c^2), with
	
			X = b(z-r)-c(y-q)						incidentally, X, Y, and Z (=0) are the equations
			Y = c(x-p)-a(z-r), and					of the projections of the line on the coordinate
			Z = a(y-q)-b(x-p)						planes (I think ...)
			
	I am sure your formula for a point on the line actually computes the distance and is equivalent to the above.
	
Distance d between line l and l':

	Set (by analogy with your notation), Dxy = ab'-ba', Dyz = bc'-cb', Dzx = ca'-ac'. Then
	
	d^2 = [Dyz (p-p') + Dzx (q-q') + Dxy (r-r')]^2 / (Dyz^2 + Dzx^2 + Dxy^2).
	
Unfortunately this representation may not mesh so well with homegeneous representations for points and planes. I will ponder this some more.

Thanks to both you and Lyle for the discussion of Grassmann manifolds. It was amost entirely new to me and quite informative.

	L.
	*start*
03553 00096 US 
gvMsgID: gnelson.pa $ 3#218@15-Dec-83 16:13:26 PST
Categories: Tracings
Date: 15 Dec 83 16:13:23 PST
From: gnelson.pa
Subject: Corner-stitching, unparsing, the predicate calculus, and guarded commands
To: CSL^, IDL^
Reply-to: Subhana.pa

A couple of months ago I resolved to keep my technical journal more neatly than before.  As a result I now have several journal entries on the above topics.  I could put these entries in the CSL notebook, but many of them are handwritten, and anyway it seems simpler just to let people know they exist and provide copies on request.  So send Subhana or me a message if you want copies of any of the following.

About corner-stitched data structures:

CGN1. Ennumeration of rectangular regions in corner-stitched data structures.  A description of the Shand-McCreight bounded space traversal algorithm for rectangular regions in corner-stitched data structures.

CGN2. Finding positions in corner-stitched data structures.  In his dealer, Mark Shand described how to home in on the tile containing a given (x, y) position, by following corner-stitches in the direction of the goal. But since, in such a data structure, northward movement is accompanied by east-ward drift, and westward movement is accompanied by southward drift, it is difficult to tack towards the north-west.  (Or south-east.)  Apparantly none of those who have used this data structure have bothered to prove that the loop terminates.  This note supplies something of a proof.  

CGN3. A correction to CGN2.  This note records an observation of Jim Saxe that was relayed to me by Lyle Ramshaw: that a theorem of Leo Guibas and Frances Yao provides a simpler proof than that presented in CGN2.  CGN3 records the new proof.

CGN6.  Correcting the Correction.  In CGN3 I transcribed Leo and Frances' proof, translating it from English into the predicate calculus as I did so, since this is the style of proof that I prefer. But I made a mistake, which Howard Sturgis found.  CGN6 presents a correct proof.

About the predicate calculus and guarded commands

CGN4. Combining Satisfiability Procedures by Equality Sharing.  This describes a simple method for combining theorem-provers for different theories into a combined theorem-prover for the combined theories.   The method is used in the heart of the Juno 2 interpreter, to coordinate the application of the geometric constraint-solver and the pattern-matching constraint solver. 

CGN5. Predicate Algebra.  An introduction to the predicate calculus, as I understand it.

CGN7. From predicates to relations and functions.  This is a continuation of CGN5, discussing the treatment of partial functions.

CGN10. Guarded Commands in 53 easy steps.  This is a summary of the programming notation that I use.

About unparsing or pretty-printing

CGN8.  Unparsing.  This note describes an algorithm for unparsing (or pretty-printing). The algorithm is interesting because it makes non-trivial use of exception-handling.

CGN9.  Unparsing continued.  As part of the Juno system I have implemented a general-purpose formatting package, which Mike Spreitzer has connected to IO to yeild formatting IO streams, which accept formatting commands as well as characters.  CGN9 applies the general method of CGN8 to the particular formatting commands used in Mike's and my package.  If you want to really understand the formatting codes, you probably have to read CGN8 and CGN9. 
�Êd˜JšÐbsœ˜Jš�œ˜Jš�œK˜RJš�œ˜Jš�œ˜J˜Jšœ›Ïi&œ¬
ž1œ¿ž$œï˜ð—…—

‚*start*
03166 00096 US 
gvMsgID: stolfi.pa $ 89#132@16-Dec-83  8:26:47 PST
Categories: Tracings
Date: 16 Dec 83  8:26:23 PST
From: stolfi.pa
Subject: Re: Lines in space, 2-nd message
In-reply-to: "Guibas' message of 14-Dec-83 12:55:24 PST"
To: Guibas
Cc: Stolfi, Ramshaw

Leo, thanks for the lecture. I knew I was missing something trivial...

I have spent some time trying to extend the (p,q,r//a,b,c) representation to include lines at infinity, without much success. Frustrating; it seems so close...

On the other hand, I think I have found an identity that my six coefficients Aij must satisfy, namely AxyAzw - AxzAyw + AxwAyz = 0.  Now let

  Axy = Pxy + Qzw,	Azw = Pxy - Qzw,
  Axz = Qxz - Pyw,	Ayw = Qxz + Pyw,
  Axw = Pxw + Qyz,	Ayz = Pxw - Qyz

(i.e., Pxy = (Axy +Azw)/2, Qzw = (Axy - Azw)/2, etc.) Then the identity becomes

   Pxy^2  - Qzw^2  -  Qxz^2 + Pyw^2  + Pxw^2 - Qyw^2 = 0

or

  Pxy^2  + Pyw^2  + Pxw^2   =   Qzw^2 + Qxz^2 + Qyw^2

If P's and Q's are any real numbers satisfyng this identity, then the P's are all zero iff the Q's are all zero. There is a one-to-one correspondence between the PQ's and the A's, and the former are all zero iff the latter are all zero. Note also that scaling all P's and Q's by a constant does the same to the A's (and therefore leaves the line unchanged).

This suggests representing a line by six numbers <P1, P2, P3//Q1, Q2, Q3> such that not all three P's are zero, and not all three Q's are zero, with the convention that

   (Pxy, Pyw, Pxw)  = (P1, P2, P3)/sqrt(P1^2+P2^2+P3^2)
   (Qxy, Qyw, Qxw) = (Q1, Q2, Q3)/sqrt(Q1^2+Q2^2+Q3^2) 

From these we can compute six non-zero A's satisfying the identity above.  Another sextuplet <P1', P2', P3'//Q1', Q2', Q3'> produces the same A's (with the same signs) iff

   (P1', P2', P3') = alpha(P1, P2, P3)
   (Q1', Q2', Q3') = beta(Q1, Q2, Q3)

with alpha > 0, beta > 0. (If alpha < 0, beta < 0 it will produce the negatives of those A's) 

This is all very nice (assuming I didn't make some horrible mistake in the derivations above), but I still have to check  whether every set of A's generated by this process corresponds to some line, and whether those lines are all distinct. Note that the collection of those A's is a four-dimensional manifold, so there can be any other identities to be satisfied, nor degrees of freedom.  There may be pathological subsets of smaller dimension, though. 

In fact, there are hints that something must be wrong. If the representation above were really one-to-one, then the set of all ORIENTED lines in two-sided projective three-space, that we know is the oriented Grassmann manifold G'4,2, would be homeomorphic to S2 x S2 (the sphere squared), which would be surprising. (Also, the set of the NON-ORIENTED lines in classical projective three-space (~G4,2) would be obtained from S2 x S2 by identifying every pair (p,q) with (-p, -q). This doesn't seem to be P2 x P2, so maybe there is still some hope...).

Well, I guess I should think more and write less. Watch this space for new developments.

jorge
�Êq˜JšÐbsœ˜Jš�œ˜Jš�œ"˜)Jš�œ-˜8Jš�œ˜
Jš�œ˜J˜J˜GJ˜ 
J˜¦J˜õJ˜ÇJ˜§J˜YJ˜—…—ˆÿ*start*
02005 00096 US 
gvMsgID: stolfi.pa $ 89#132@16-Dec-83  9:22:34 PST
Categories: Tracings
Date: 16 Dec 83  9:22:21 PST
From: stolfi.pa
Subject: Analytic tracings
To: Ramshaw
Cc: Guibas, Stolfi

Some time ago you made me notice that two analytic pieces of tracings (two functions r(t), s(t) from some time interval (-epsilon, +epsilon) into the set of states, such that both position and orientation are anlytic in that interval) may agree for t>0 but not for t<0.  For example, let r be a move at constant speed, and s(t) = r(t^2). I believe this was one of the reasons you had for working with `state-leaving' germs instead of 'state-crossing' ones. 

For reasons I don't remember clearly now, I thought of defining a subfamily of tracings where each arc is characerized by two analytic functions from [0 1] to R, namely lambda(t) = (forward traversed arc length minus backwards traversed arc length from time 0 to time t), and theta(t) = (radians of left turn minus radians of right turns from time 0 to time t).  The arcs are further restricted by saying that no instant t0 (including 0 and 1) may be a local extremum for both lambda and theta. That is, at last one of them must have taylor expansion of the form a + b (t-t0)^k + ..., with a,b neq 0 and k odd.

This requirement rules out tracings of the form s(t) = r(t^2). The question is, is it too restrictive? For example, consider the tracing defined by lambda(t) = t^4 + t^17, theta(t) = t^10.  This is analytic (in your sense, too) but does not satisfy the requirement above at t=0. Is it possible to reparametrize it as
 lambda*(s) = s^2 + ...
 theta*(s) = s^5 + ...
so that both are analytic in s? 

(Sorry if this is a dumb question --- I am no longer functioning by now.  I have been keeping an owlish schedule this week, and it is already a couple of hours after my bedtime.)

Hope to see you Monday (rather than Monnight),

jorge 

�Ê^˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ	˜Jš�œ˜J˜ËJ˜ãJ˜�J˜³
J˜/J˜—…—v*start*
02585 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@16-Dec-83 13:44:51 PST
Categories: Tracings
Date: 16 Dec 83 13:44:43 PST
From: Ramshaw.pa
Subject: Re: Analytic tracings
In-reply-to: "stolfi's message of 16 Dec 83  9:22:21 PST"
To: stolfi
Cc: Ramshaw, Guibas

Jorge, you present several interesting ideas, and I'm not sure that I understand them completely.  For example, I had never considered describing a curve by giving the car's heading and the cumulative signed arc length that it has traversed as real analytic functions of time, as you propose.  But I think that I do understand enough to show that your proposal to demand that these two functions don't achieve simultaneous local extrema is, sad to say, too restrictive.  Suppose, for example, that lambda and theta are related by the algebraic equation:

	(theta-lambda^2)^2 = lambda^5.

The path lambda(t)=t^2, theta(t)=t^4+t^5 solves this equation.  But both lambda(t) and theta(t) have local minima at t=0 along this path.  I claim that no reparametrization can avoid this.  The reparametrized versions of theta and lambda would still have to solve this algebraic equation.  And it isn't hard to show that there are no solutions to this equation with lambda and theta both small real numbers other than the solutions that correspond to small real t in the above parametric form.  Proof:  Lambda can't be negative, because it's fifth power is the square of a real number.  Next, if we fix lambda at some small positive real value, the remaining equation is quadratic in theta;  thus, at most two values of theta can exist, even over the complexes.  But the parametric form already accounts for two values of theta, namely 

	theta = lambda^2 + lambda^(5/2)   and   theta = lambda^2 - lambda^(5/2),   

corresponding to t=lambda^(1/2) and t=-(lambda)^(1/2) respectively.  Thinking geometrically, there are two curved paths leaving the origin that are solutions to the algebraic equation, both initially tangent to the lambda-axis and curving into the first quadrant.  The "through germ"

	lambda(t) = t^2, theta(t) = t^4 + t^5

comes in on path A and leaves on path B.  The "through germ"

	lambda(t) = t^2, theta(t) = t^4 - t^5

comes in on B and leaves on A.  The "through germ"

	lambda(t) = t^4, theta(t) = t^8 + t^10

comes in on A and leaves on A.  The "through germ"

	lambda(t) = t^4, theta(t) = t^8 + t^10

comes in on B and leaves on B.  But they ALL involve simultaneous minima in both lambda and theta at t=0.

Lyle

�ÊX˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ.˜9Jš�œ˜
Jš�œ˜J˜J˜µ—…—	^	¼*start*
00507 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@16-Dec-83 13:49:26 PST
Categories: Tracings
Date: 16 Dec 83 13:49:10 PST
From: Ramshaw.pa
Subject: PS to Re: Analytic tracings
In-reply-to: "stolfi's message of 16 Dec 83  9:22:21 PST"
To: stolfi
Cc: Ramshaw, Guibas

I just noticed a typo in my recent message:  the last of the "through germs" should have had theta(t) equal to t^8 MINUS t^10, not plus.

Lyle


�ÊX˜JšÐbsœ˜Jš�œ˜Jš�œ˜$Jš�œ.˜9Jš�œ˜
Jš�œ˜J˜J˜�
—…—
@
ž*start*
04334 00095 US 
gvMsgID: Guibas.pa $ 3#183@16-Dec-83 18:02:06 PST
Categories: Tracings
Date: 16-Dec-83 18:01:37 PST
From: Guibas.pa
Subject: another view of discretized tracings
To: dke@sail
cc: Ramshaw, Guibas, Stolfi

There are several possibilities for a calculus of discrete, or "rasterized", tracings. To examine some of the options, it may be useful to recall some of the earlier steps in the evolution of polygonal, or analytic, tracings.

For a long time we lived with the idea of a tracing as a manifold of the state space. We regarded a tracing as a smooth mapping of some "uhr"-space (typically a collection os S^1's) into a state space (typically R^2\times S^1). There were problems with this view, for, in a sense, it supplied too much information: it made us distinguish tracings that operations like convolution and product forced us to regard as the same. The essence of the challenge was that we were to describe how often the car entered and left each state in various modes, but not fixate on any pairing between ways of entering and ways of leaving. In the current kinetic paper we accomplished this by defining tracings via counting functions. Of course in doing this we lost the manifold view, and along with it any notion of the dimensionality of the tracing, except in the very special polygonal case.

When we look at the discrete domain, and until we understand things better, it may be wise to return to the manifold language. We all agree about the image space for the location component: it is the integer lattice. But there are some questions as to what should be the image space for directions, and, even more important, what the "smooth" mapping defining the manifold should be. The approach that you and Lyle arrived at yesterday is a natural one. It is the standard manifold view, when the car is resticted to move on a system of roads laid down according to a Manhattan geometry. As Lyle's analysis points out, this can probably be made to work, but it is cumbersome. The car's direction is wiggling an awful lot because its position is confined to follow the grid. Unfortunately all these turns pair up with the moves of another tracing under convolution to produce a somewhat unwieldy result. Noise beats against noise to generate even more noise.

Another possibility is suggested from the view of a state as a position, and an oriented line containing the position (we have to thank the duality for this). Again, there's unanimity on how to rasterize positions. For the other component, let us restrict our attention to rasterized lines, specifically the rasterizations (according to Bresenham) of ideal lines connecting grid points. So to define a tracing we have to give a "smooth" mapping of something into the set of pairs (grid point, oriented rasterized line containing the point). It is not clear what the best "uhr"-space here would be; perhaps the rationals, or some other countable set. Imagine that the car is at a grid point when the manifold variable t is at an integer, and it "smoothly" turns between lines of rational slope when t is fractional (mumble). The concepts of move and turn can be rigorously defined, and therefore the concept of a rasterized polygonal tracing. The nice thing of course is that these tracings include all rasterized tracings one might want -- just make the number of sides sufficiently (but finitely) large. I am pretty sure such tracings are closed under the standard operations. Also, a discrete analog of convexity can be defined and, I believe, the convolutional and classical analogs of the continuous definitions agree. Convolution of convex tracings is convex, etc.

I doubt this view is panacea for all problems. The specification of direction by a rational slope is especially bothersome, but is seems to be the price that has to be paid for the elimination of excessive wiggliness. One can hope to also recapture some of the continuous orthogonality constraint between position and direction by picking some integer threshold k and then demanding that whenever a tracing from a point x on follows in position a rasterized line by k or more steps, then the tracing's direction at x must be the same or the opposite of the rasterized line in question.

Probably no discrete view of tracings is self-dual.

End of endless discussion ...*start*
01242 00096 US 
gvMsgID: stolfi.pa $ 89#132@19-Dec-83  9:19:59 PST
Categories: Tracings
Date: 19 Dec 83  9:19:37 PST
From: stolfi.pa
Subject: Re: Analytic tracings
In-reply-to: "Ramshaw's message of 16 Dec 83 13:44:43 PST"
To: Ramshaw
Cc: stolfi, Guibas

Lyle, thanks for your message; I am sorry for wasting your time with such dumb questions. I must have been real sleepy Friday morning. I recall having considered the very same example you gave, but I messed up the algebra somewhere, and I concluded it had some analytic reparametrization of the form lambda(s) = s + O(s^2), theta (s) = s^2 + O(s^3). Shame on me.

Anyway, I am not that sad the conjecture is false.  I thought of it while trying to generalize my current ideas on circular tracings (for which, incidentally, ``through'' germs seem to work fine).  On Friday morning I thought the family of analytic-without-local-minima tracings would have some of the nice properties of circular tracings.  I am still thinking about that.  It would have been nice if that family were the same as the general analytic tracings, but of course that is not so.

Thanks again,

jorge
�Ê_˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ/˜:Jš�œ	˜Jš�œ˜J˜J˜ëJ˜ëJ˜—…—{*start*
00389 00096 US 
gvMsgID: stolfi.pa $ 89#132@19-Dec-83 10:46:22 PST
Categories: Tracings
Date: 19 Dec 83 10:46:05 PST
From: stolfi.pa
Subject: Re: discretized tracings
To: Guibas
Cc: stolfi

Leo, 

I didn't get a copy of dke's original message. Would it be possible to send me one?

thanks,
jorge
�ÊN˜JšÐbsœ˜Jš�œ˜Jš�œ˜!Jš�œ˜
Jš�œ˜
J˜J˜i—…—Ò
&*start*
03487 00096 US 
gvMsgID: stolfi.pa $ 89#132@20-Dec-83 22:48:22 PST
Categories: Tracings
Date: 20 Dec 83 22:48:03 PST
From: stolfi.pa
Subject: Lines in space
To: Guibas, Ramshaw
Cc: stolfi

I have checked my algebra again, and I still believe in it: the set of oriented lines in two-sided three-space is indeed homeomorphic to S2 x S2, i.e. every line (including the ones at infinity) can be represented uniquely as a pair of unit vectors (p,q) in R^3.

One possible way to establish the correspondence is the following: the line defined by (p,q) is always orthogonal to the vector p-q.  If q neq -p, the line is "finite"; it is parallel to the vector p+q, lies on the perpendicular bisector B of pq, and its distance from the origin is

  d = tan (angle(p,q)/2);

more precisely, it passes through the point

  u = - (p x q) / (1 + p . q) 
  
(where x is vector product and . is dot product).

If p = -q, the line is at infinity: it is the intersection of the plane at infinity with the perpendicular bisector B of p and q, and oriented counterclockwise with respect to an observer standing on B at the origin with p pointing up.

It is obvious that the line changes continuously with changes in p and q, as long as q does not pass through -p. To analyze what happens this case, note first that the bisector plane B is well defined and continuous for q near -p.  As q goes to -p, the line moves off to infinity, always oriented counterclockwise as seen by an observer standing on B at the origin and with p-q pointing up. Let us say that the line is oriented "northwards" and moves "westwards".  When p=-q, the left side of the line is the entire "top" side of B. (Note that B is a two-sided plane.) If q passes "straight" through -p, the line reappears on the "far east", oriented "southwards". In the two-side plane geometry of B, this is a continuous motion; note that the the line remains oriented counterclockwise with respect to the observer, so that the origin is still on the left half-plane determined by L on B.  

Conversely, the vectors p and q are uniquely determined by the line L: if L is at infinity, take p = -q = its counterclockwise normal; if L passes through O, take p = q = its orientation vector; otherwise, take p and q so that p+q is parallel to L, p-q is perpendicular to the plane LO and oriented counterclockwise from L, and p makes an angle of arctan(dist(L, O)) with L.

The dual of L = <p,q> is L* = <p, -q>.  The opposite of L is <-p, -q>.  

Is there something wrong? If this is correct, then the oriented Grassmann manifold G'4,2 is homeomorphic to S2 x S2 (could it be true???), and the non-oriented one is obtained from S2 x S2 by identifying every pair <p,q> with <-p, -q>.

It is interesting to speculate on what happens in higher dimensions.  We know that G'n,1 = G'n,n-1 = S(n-1); it is not clear whether G'n,0 and G'n,n should be S0 (two points) or (Sn)^0. In general, G'n,k is a k(n-k)-dimensional manifold.  My intuition tells me we can map every oriented linear subspace  of R^n to an oriented version of its orthogonal complement, in a one-to-one continuos fashion; if so, then G'n,k must be homeomorphic to G'n,(n-k).  Therefore G'n,k can't be (Sk)^(n-k), for this is not the same as (S(n-k))^k.  Hmmm... I guess I will stop wondering and do some research.

Thanks for listening reading,

jorge                 

�Êr˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ˜Jš�œ˜
J˜J˜‡J˜¥J˜ýJ˜÷J˜IJ˜ì
J˜ÏJšœÏy	œ"˜6—…—È
@*start*
00898 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@ 3-Jan-84 17:11:11 PST
Categories: Tracings
Date:  3 Jan 84 17:10:19 PST
From: Ramshaw.pa
Subject: tracings and all
To: Stolfi
Cc: Ramshaw, Guibas

Jorge, I took a glance at the Klingenberg paper;  it's on my desk if you want it back.

Leo and I worked through the case of taking the product of two tracings A and B where A consists of a circle travelled m times and B is a circle properly containing A travelled n times.  Unless we goofed things up, it appears that the Klingenberg way of choosing the additive constant in the winding number does NOT, sad to say, give w(A.B)=w(A).w(B);  but maybe some related rule does so.  After our experiences so far, I'm very fond of any rule that involves watching what happens as a car drives around the tracing,

Lyle


�ÊO˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ˜
Jš�œ˜J˜J˜æ—…—Ð%*start*
02316 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@ 4-Jan-84 16:31:26 PST
Categories: Tracings
Date:  4 Jan 84 16:28:02 PST
From: Ramshaw.pa
Subject: musings on 2SP winding numbers
To: Stolfi, Guibas
Cc: Ramshaw

Here is an update on my thoughts about winding numbers of tracings on the 2SP, stimulated by Jorge's observations of yesterday.

Define a "tracing" to be a multiset of turns and moves (or germs or whatever) together with a choice of additive constant offset for the winding number function.  We think that we know how to operate with tracings:  the offset for the sum of two tracings is set to make winding number linear;  the offset for the product is set to make the product relation hold in some region;  and the offset for the convolution is set to make the convolution theorem hold in some region.

But it is unpleasant to have to specify this offset as an extra piece of information.  One alternative would be to distinguish a special class of tracings, call them the "reduced tracings," in which the offset is determined by some rule from the geometry.  What properties would be desirable for a class of reduced tracings?

P1:  A tracing that has all of its geometry on one side of the 2SP should have reduced winding number zero around all points of the other side.

P2:  The sum of reduced tracings should be reduced.

P3:  The product of reduced tracings should be reduced.

P4:  The convolution of reduced tracings should be reduced.

Yesterday, we were considering defining the reduced winding number of a tracing to be half of the Klingenberg winding number.  This choice satisfies P2, but not P1 or (assuming Leo and I got our arithmetic right) P3;  I don't know about P4.

What about defining the reduced winding number of a tracing to be half of the Klingenberg winding number plus half of the degree?  I haven't been able to construct a counterexample to any of the four properties yet for this rule;  but I haven't given up looking either.  Note that this rule gives winding numbers of regions that aren't integers, as did the previous rule:  consider a tracing that consists of just a full line.  I was a little surprised at this at first, but I guess that there is no real problem with it.

Lyle
 

�ÊO˜JšÐbsœ˜Jš�œ˜Jš�œ ˜'Jš�œ˜Jš�œ	˜J˜J˜â—…—Z¯*start*
00812 00095 US 
gvMsgID: Guibas.pa $ 3#183@ 4-Jan-84 18:01:02 PST
Categories: Tracings
Date:  4-Jan-84 18:01:10 PST
From: Guibas.pa
Subject: Re; musings on 2SP winding numbers
To: Ramshaw, Stolfi
cc: Guibas

I like your suggestion of .5(Klingenberg+degree). Jorge observed the multilinear decomposition of tracings into three kinds of components, i.e. simple tracings doubled-up paths and full turns. Your rule is equivalent to assigning to each component the winding numbers we would classically assign. Then your rule follows by multilinearity.

This doesn't quite cover the case of the 2SP straight line, but this can be viewed as wavering between a positive large circle on the left and an negative large circle on the right. The winding numbers you get are the average of these two situations.

	Leo*start*
03132 00095 US 
gvMsgID: stolfi.pa $ 89#22@ 5-Jan-84  1:52:44 PST
Categories: Tracings
Date:  5 Jan 84  1:52:27 PST
From: stolfi.pa
Subject: Re: musings on 2SP winding numbers
In-reply-to: "Ramshaw's message of 4 Jan 84 16:28:02 PST"
To: Ramshaw
Cc: Stolfi, Guibas

Lyle, 

I have just read your message, and I haven't checked your proposal yet.  But I think you are on the right track. I have vaguely convinced myself that the Klingenberg winding number, kinetic version, is the only function (modulo an arbitrary factor) of the form w(p,T) that satisfies the following properties:

Q1.  w is "topologically" invariant, i.e.  w(p,T)=w(h(p),h(T)) for any differentiable homeomorphism of S2 to S2 .

Q2. w is additive, i.e. w(p,T+T') = w(p,T) + w(p,T'), where T+T' is the superposition of the two tracings.

Q3. w is zero for null tracings, i.e. w(p,-T)=-w(p,T), where -T is the time-reversal of T.

One consequence of Q1 is that w is "absolute", and not relative to some arbitrary reference point. It also implies that w only changes when p crosses T.  On the sphere, with the sort of equivalence considered in Q1, there is no distinction between counter- and clockwise oriented circular tracings, although we can distinguish forward from backward ones, and the left side from the right side (relative to the orientation of the car). Therefore, for any function w satisfying Q1-Q3 there are two constants x,y such that every circular tracing has winding number x on the left side and y on the right side.

Now consider a tracing T consisting of two coincident circles, both traversed forwards but oriented oppositely to each other. Because of the above, the winding number w(p,T) must be x+y for any point not on T.  Now T can also be broken into

      k simple paths P1, P2, ... Pk (each an arc of measure 2pi/k,
      traversed forwards in both senses, with turns by +pi on either end)

minus

      k full turns R1, R2, ... Rk located at the joins of those paths.

Therefore, w(p,T)=k(w(p,P1)-w(p,R1)). Since this holds for all k, w(p,P1)-w(p,R1) must be zero, and so must be w(p,T)=x+y. This proves x=-y. 

On the other hand, to get a product rule of the form w(p,AB)=w(p,A)w(p,B), where the product is defined as usual, requires the winding numbers for a forward circle to be 0 and 1. A winding number function with this property cannot be topologically invariant in the sense of Q1.  It seems we need to introduce the non-topological notion of degree, i.e. to distinguish clockwise from counterclockwise circles on the sphere. This is equivalent to distinguishing circles from straight lines (great circles).

In other words, we want w to be invariant only under homeomorphisms of S2 to S2 that preserve orientation and map great circles to great circles. These correspond to the projective mappings of the 2SP, i.e. the non-singular linear transformations of R^3 (acting on the homogeneous coordinates of the points). 

Well, enough ramblings for today. See you tomorrow,

jorge
�Ê‚˜JšÐbsœ˜Jš�œ˜Jš�œ$˜+Jš�œ.˜9Jš�œ	˜Jš�œ˜J˜J˜½J˜rJ˜kJ˜[J˜ÞJ˜ñ
J˜�
J˜J˜GJ˜Ž
J˜øJ˜¶J˜:—…—VÞ*start*
00835 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@ 5-Jan-84  9:48:25 PST
Categories: Tracings
Date:  5 Jan 84 09:48:19 PST
From: Ramshaw.pa
Subject: Re: musings on 2SP winding numbers
In-reply-to: "stolfi's message of 5 Jan 84  1:52:27 PST"
To: Stolfi
Cc: Ramshaw, Guibas

I agree that full topological invariance (Q1) is too strong a property to ask for.  In fact, under the definitions that I was assuming, arbitrary homeomorphisms of S2 wouldn't even take tracings to tracings, necessarily.  In order to be able to compute convolution, I was assuming a requirement that tracings be transverse to the line at infinity;  and this property is not invariant under homeomorphisms.  It is invariant under projective mappings of the 2SP.

Lyle

�ÊX˜JšÐbsœ˜Jš�œ˜Jš�œ$˜+Jš�œ-˜8Jš�œ˜
Jš�œ˜J˜J˜Ó—…—ˆæ*start*
02466 00095 US 
gvMsgID: stolfi.pa $ 89#22@ 5-Jan-84 20:35:07 PST
Categories: Tracings
Date:  5 Jan 84 20:34:55 PST
From: stolfi.pa
Subject: Re: daily ramblings (on 2SP winding numbers)
In-reply-to: "Ramshaw's message of 5 Jan 84 09:48:19 PST"
To: Ramshaw
Cc: Stolfi, Guibas

"I was assuming a requirement that tracings be transverse to the line at infinity;  and this property ... is invariant under projective mappings of the 2SP."

Actually, by means of a projective mapping you can move any line to the line at infinity. You probably mean affine mappings.

I believe that if h is an analytic, non-reversing homeomorphism of S2 to S2, then the image of a tracing T under h can be defined in a natural and unambiguous way. In fact, I would guess this is true of piecewise analytic homeomorphisms,too.  

The reason I am interested in "foobar numbers" that are topologically invariant in some strong sense is that properties such as discrete-valuedness then come for free. What is more, such numbers can be defined by giving their values for a small collection of elementary  tracings. So, for piecewise analytic homeomorphisms we have to consider only {circle, doubled-up path,  full turn}, traversed forwards and with turns to the left. (I propose to call faces, edges and vertices the images of these tracings under p.a. hom.s.)

If we want to define winding numbers and degree only for polygonal tracings, then invariance under non-reversing projective mappings is enough. I believe in this case a sufficient set of non-equivalent primitive tracings is {ccw proper triangle, doubled-up proper segment, full turn}, traversed forwards and with turns to the left (we can get all other polygonal tracings by decomposition and signed sum).

On the other hand, for general analytic tracings that are transverse to the line at infinity I would consider foobar numbers that are invariant under any non-reversing piecewise analytic homeomorphism that maps the line at infinity onto itself. In this case the set of primitive tracings would have to be larger, e.g. {ccw circle on top, ccw circle on bottom, ccw circle crossing the line at infinity twice, doubled path on top side, d. p. on bottom, d.p. crossing the line once, turn on top, turn on bottom} (or something of the sort).

See you,

 jorge  
�Êš˜JšÐbsœ˜Jš�œ˜Jš�œ.˜5Jš�œ.˜9Jš�œ	˜Jš�œ˜˜J˜ž
—J˜}JšœÏi	œ©
ž	œ ˜ô
JšœÅžœžœžœ1˜�Jšœ9ž	œÔ˜–J˜™J˜	J˜—…—¤	D*start*
01902 00095 US 
gvMsgID: Guibas.pa $ 3#183@ 5-Jan-84 23:21:39 PST
Categories: Tracings
Date:  5-Jan-84 23:21:39 PST
From: Guibas.pa
Subject: Tracings on the sphere
To: Stolfi
cc: Guibas, Ramshaw

Piecewise analytic mappings may introduce new corners, so I don't see why the image tracing is unambiguous.

Do you mean by "discrete-valuedness" that points that can be connected by a path which avoids the tracing must have the same "foobar" value?

It is worth exploring if there is a proper way to define degree and sweep numbers on the sphere in a way that gives them a certain topological invariance. For one, degree is just the sweep number of a point on the line at infinity, which is no longer special on the sphere. Among other things this implies that convolution is not a topologically invariant concept, since its definition depends on the choice of a line at infinity, while sum and product are. We had a way of giving a topological definiton of the difference in sweep number between two points based on a homotopy family of paths between the two points, so we are back to the same problem as with winding numbers, that of a floating origin. Perhaps these numbers too will turn out to be another multiple of the Klingenberg wn's.

Another approach might be based on defining a class of positive tracings. I am not sure yet how to do this, but such a class of tracings should be closed under addition, product and convolution, and have everywhere non-negative winding and sweep numbers. For such a class of tracings we can try to define the degree as delta = \sum{delta!i}, where delta!i is the number of connected components of the area of the plane with winding numbers i or greater. Perhaps these can be the tracings obtained by taking positive linear combinations of analytic images of the fundamental tracings as envisioned by you.

�Ê(˜Jšœ¹	Ïeœž˜ß
—…—â*start*
03035 00095 US 
gvMsgID: stolfi.pa $ 89#22@ 6-Jan-84 17:28:10 PST
Categories: Tracings
Date:  6 Jan 84 17:28:11 PST
From: stolfi.pa
Subject: Re: Tracings on the sphere
In-reply-to: "Guibas' message of 5-Jan-84 23:21:39 PST"
To: Guibas
Cc: Stolfi, Ramshaw

Leo,

My intuition about piecewise analytic homeomorphisms (pahs) may be wrong,  but I still believe that the image of tracings under them is well-defined.  My definition of a pah is a function h of S2 to S2 such that (1) h is one-to-one, (2) h is analytic in some finite number of closed regions R1,R2,...Rn whose union is S2, and (3) the inverse of h is analytic in h(R1), h(R2),...,h(Rn).

A piecewise analytic mapping h may introduce new corners only at points p where T crosses the boundary between two distinct "regions of analicity" R1, R2 of h.  The orientation and sense of traversal of h(T) just before and after h(p) have a natural and unabiguous interpretation, so the turn of h(T) at h(p) is determined only up to an integer number of full turns. This offset is determined by counting the signed number of times the tangent of T sweeps through the tangent of the R1-R2 boundary as the car turns at p, and adding enough full turns to h(T) to make the count come out the same.

Another (an perhaps more precise) way of saying this is the following. Let b1, b2 be the two branches of the R1-R2 boundary leaving the point p. First, define the image of a 180 degree left turn at p from the direction of b1 to that of b2 to be the 180 deg. left turn from h(b1) to h(b2), and similarly for half-turns from b2 to b1.  Let d and d' be the orientations of T just before entering p and just after leaving it, respectively.  Now, we can always describe the turn of T at p (if any) in a unique way as a left turn by a proper angle from d until the car is parallel to some bi (i=1 or 2), plus some signed number n of left half-turns, plus a proper left turn from the bj thus reached to d'.

Now consider the behavior of h(T) in the neighborhood of h(p). I may be wrong, but I believe that h(T) must reach h(p) with its orientation D making a proper angle with h(bi). Similarly, it must leave h(p) with its orientation D' making a proper angle with h(bj). (This would be false if d were parallel to b1, while D were parallel to h(b2), but here faith comes in: I believe no pah can do that) The turn of h(T) at h(p) is then by definition the proper left turn from D to h(bi), plus n left half-turns, plus the proper left turn from h(bj) to D'.

The case where T switches regions at a vertex is a bit more complex, but my faith is still strong enough to handle it.   

My intuition tells me in particular that a pah never creates or destroys a cusp; more generally, it never adds or subtracts a full half-turn (or more) to any turn. A counterexample would make mincemeat of the above arguments.

jorge
�ʧ˜JšÐbsœ˜Jš�œ˜Jš�œ˜#Jš�œ,˜7Jš�œ˜
Jš�œ˜J˜Jš
œ˜Jšœ”Ïbœh˜‚J˜ÓJšœòžœžœtžœ+˜¼Jšœ—
žœRžœ²˜§Jš
œz˜zJš
ω
˜â
J˜—…—
Ð}*start*
00750 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@31 Jan 84 11:49:59 PST
Categories: Tracings
Date: 31 Jan 84 11:50:05 PST
From: Ramshaw.pa
Subject: convolution query from DEK
To: Stolfi
Cc: Ramshaw

Jorge, Don suggests the following conjecture:  If A and B are tracings with only nonnegative winding numbers and with no backward moves, then 
	i) A*B has only nonnegative winding numbers, and
	ii) A*B has backward moves only in its "interior", that is, A*B has no backward moves adjacent to regions of zero winding number.

Any ideas on this?  If it's false, perhaps the weaker version where at least one of A or B is required to be convex would be true,

Lyle
 

�ÊO˜JšÐbsœ˜Jš�œ˜Jš�œ˜#Jš�œ˜
Jš�œ	˜J˜J˜Ð—…—<‘*start*
01348 00094 US 
gvMsgID: Ramshaw.pa $ 3#8@31 Jan 84 13:56:38 PST
Categories: Tracings
Date: 31 Jan 84 13:56:29 PST
From: Ramshaw.pa
Subject: convolution conjecture
To: DKE@SU-AI, Stolfi
Cc: Ramshaw

Don, I've only had a few minutes to think about your conjecture so far, and there seems to be something in it.  But in the bald form that I wrote it down after our phone conversation, it isn't hard to generate a counterexample.  Let the tracing A be the normal description of an annulus with radii R and r;  that is, it consists of a circle of radius R traversed by a car driving forward and counterclockwise in combination with a circle of radius r traversed by a car driving forward and clockwise.  Let the tracing B be the normal description of a simply enormous disk of radius E;  that is, B consists of a circle of radius E traversed forward and counterclockwise.  Both of these tracings involve only nonnegative winding numbers, and neither of them includes any backing up.  The convolution of A and B consists of two circles:  one traversed forward and counterclockwise of radius E+R;  and one traversed backward and clockwise of radius E-r.  The inner circle is the boundary between regions of winding number one and winding number zero.

Lyle

 
�ÊO˜JšÐbsœ˜Jš�œ˜Jš�œ˜Jš�œ˜Jš�œ	˜J˜J˜ž—…—’ç