ripped off by the evil empire

[Geoffrey Dutton <dutton@spatial-effects.com>]

Hi,
Yesterday was my first day on this list, so I perused the archives to get
the feel of it, and feel I am talking to the right people here. I have a
problem that I hope will interest someone enough to help me a little, and
maybe I can help others avoid similar problems of their own.

Before going any farther, I am requesting each of you to *not* communicate
any of the following to the press, publish it yourself or transmit it to
any third party without consulting me first. I realize I can't control who
reads postings to this list, but it would be extremely sleazy and insulting
if someone exploited my situation for their own gain. I've had enough of
that already, as you'll see.

Most of my work for the past 25 years or so has been in computer mapping
and geographic data handling. I've developed cartographic and data modeling
techniques that are recognized in my field, although most have been ideas
or prototypes that were never commercially distributed. I've authored and
edited publications that are assigned in college and graduate courses, as
well as written for trade magazines.

Around 1980, I began a series of explorations in spatial data modeling in
which I treated the earth as a polyhedron which is recursively and
regularly triangulated to represent, store and query various forms of
geographic data (I based the model on an octahedron, the faces of which are
subdivided to create a forest of eight triangular quadtrees). Starting in
1983, I published a series of papers in conference proceedings, journals
and a trade magazine describing aspects of this approach, which evolved
into its current form around 1988. These reports inspired several other
researchers to construct similar models that tended to differ from mine
(called quaternary triangular mesh or QTM) in only a few minor respects.
The papers these people wrote cite me, although not always most
appropriately, and I have cited them in my Ph.D. dissertation, published
last year.

Prior to my thesis, I described QTM's properties in detail but did not
publish any code for it except for a utility function or two and a map
projection algorithm. I held back in case I wanted to work with a software
vendor to build a system based on the model as a data storage and indexing
mechanism. At some point in the early 1990s I thought about patenting it,
but by then I had written so many articles about it and seen others begin
to adopt it, that I assumed the idea was well-disclosed. Also, it was my
impression then that patents could only be issued for "useful devices", not
concepts or algorithms. I also realized that any implementation of QTM
would quickly be succeeded by a series of revisions that might not be
covered by an initial protection. So I let it go and continued to explore
and refine techniques.

In the fall of 1995 I began my doctoral residence at the University of
Zurich, researching the use of QTM in map generalization. Less than two
months later, I got an email message from an acquaintance, a manager at
Microsoft, telling me that they were "using some of my ideas" and dangling
the possibility of employment. When I followed up, I got no further
details, and after a while I stopped asking. I assumed the ideas referred
to involved QTM, and had something to do with mapping applications, but I
had no way of finding out and then got very busy with my research, coding
and writing.

It wasn't until the spring of 1997 that I was able to visit this person at
MS, at which point I found out what was going on. I was told that their
group, having read papers I had written on QTM, created an implementation
of it which became the spatial data indexing mechanism for the Encarta
Atlas 1.0. While this was the sort of thing I had hoped might happen in
general, I was rather insulted that MS chose not to reward or even
acknowledge my contribution. It would not have hurt them at all to retain
me as a consultant, and in doing so I would probably have been forced to
sign a contract indemnifying them from any IPR claims I might have. But
they didn't.

When I ran into my MS contact at a meeting last fall, I said I was
displeased, and would like formal acknowledgement for my contribution to
Encarta Atlas. We agreed it would be the right thing to do, and I was
offered a credit in the next rev of the product (which was claimed to have
been inserted shortly thereafter, but the current rev was in Beta already),
and a letter to formally acknowledge and thank me. Of course, the letter
never came. I returned to the US shortly after that conversation, and have
requested a letter several times (via email) but I stopped getting
responses, and let it slide for a few months, during which I put together
my own website to describe my research and market myself as a
geodata/cartography consultant.

Yesterday, after I learned about the public-domain.org website, I explored
it as well as I could (given it is being revised), and as a result found my
way to the USPTO website. I spent about 15 minutes doing keyword searches
to see if anything like QTM had been registered, and discovered a patent
assigned to Microsoft Corporation, applied for in April 1996 and granted in
July 1998. This patent contains 20 claims for technology used in the
Encarta Atlas, including aspects of user interface, system configuration,
defining and displaying fields of view and data modeling. It references a
"hybrid-quad-tree data structure" and illustrates it in four drawings. The
structure is that of QTM, and even the projection shown is one I invented,
which I described in a paper published in 1991. While certain aspects of
the MS implementation differ from what I have done, and the patent language
tends to obscure its provenance (e.g., they say "eight-sided polyhedron"
instead of "octahedron", which in fact it is), it appears to me that
Microsoft has patented QTM (they may have also filed other related patents
I haven't found yet).

OK, now you're up to speed. IF you are still reading, I would like to hear
some opinions on what MS did and what I might do. Specifically,

1. How is it possible to obtain a patent for something that has been publicly
   disclosed (by either oneself or others) in the literature? (I can cite at
   least 6 papers beside mine that describe something like or derived from QTM)

2. Can one patent a quadtree (or other data structure) as such, or only in
   the context of a device that serves some useful purpose? (I noticed other
   patents where "quadtree" occurs but did not read them yet).

3. If I market software based on QTM, might I be forced to pay royalties to
   Microsoft? (I have such code but no present plans to market it)

4. If I put a demo of QTM on my website, might I be in violation of the
   Encarta Atlas patent? (which specifically covers a CD-ROM product)

5. What might it take to invalidate a given patent, or portions of it?
   (in this case there is only one claim that seems to apply, and it only
   refers to "identifying said memory blocks in hybrid-quad-tree format",
   but there is more detail later on, where drawings are discussed)

6. Is it possible to revise a current patent to include additional inventors?
   (i.e, if I can't beat 'em, join 'em and ask for royalties?)

7. Is there any point in trying to bring this to the attention of the US DOJ,
   or is the MS suit too far along?

Sorry to go on so long. If this situation interests you, you might take a
look at descriptions of my work with QTM (including summaries, animations
and PDFs) on my site: http://www.spatial-effects.com/SE-research1.html/

I will very much appreciate any informed responses, either to me personally
or to the list if it's of general interest. Again, please do not
communicate any of the above to third parties without obtaining my
permission beforehand. Thanks for indulging me.

-Geoff Dutton

   __________________________________
  |                                  _________________________________
  | S      p     a    t   i  a l         E      f     f    e   c  t s |
  |                                                                   |
  |        m i n d i n g   t h e   m e a n i n g   o f   m a p s      |
  |                                                                   |
  | info@spatial-effects.com                                          |
  | 20 Payson Rd.  Belmont  MA 02478  USA         T/F +1-617-489-4524 |
  |_________________________________  http://www.spatial-effects.com/ |
                                    __________________________________|