nosoftwarepatents-award

English

Deutsch

Home

Software Patent
of the year 2006

April – Patent 2

EP1085461 – Method of Handling Tree Data Structures for Spatial Navigation

EU-Patent on Software (algorithm)
Application with European Patent Office by Franck Jean Frédéric Perdrizet (France)
Granted on 12/28/2005
Patent specification provided by FFII/Gauss
Patent specification provided by EPO/espacenet

Advice on the reading of patent specifications:

The decisive element are the claims, as they specify which actions are forbidden within the framework of the patent.
Violating one single claim is sufficient to be considered a patent violation. Generally, claim number 1 is the decisive main claim which covers all other claims relating to special cases.
The description is intended to help the reader interpret the claim. At the same time, it is supposed to document and disclose the details of the invention. This disclosure is the original purpose of the entire patent system.
In practice, a patent specification contains no detailed information on how the patented procedure could be implemented (even if the patent owner allowed the implementation). In particular, a software patent contains no program code (reference implementation), but merely describes the idea of a software.

Patented idea: Using Tree Data Structures for Spatial Navigation

Main claim: A map is divided into one or several levels of grid cubes ("digital grid cells") which are administrated in a tree data structure. In this way, length, width and height are combined into a single "ternary coordinate" (index within the tree data structure).

Other claims:

Performance of shifting operations in ternary coordinates
Performance of zoom operations in ternary coordinates by prefix/suffix
Representation of a view of 3x3 grid cells
Shifting/zooming of the view by means of ternary coordinates
Extension of the 3x3 view by further rings
Control surface for shifting operations

Description: The patent specification explains, similarly as any programming textbook, the terms "tree data structure" and "ternary coordinate" and discusses the pros and cons of this type of data storage.

The word "level" is used in the patent specification in two different meanings: on the one hand, in the spatial sense, as height indication and, on the other, as designation of the recursion depth within the tree data structure.

Everyday parallel:

Tree data structure, ternary coordinate: I ask the captain of a freighter where a certain box is within the cargo, and I get a tree data structure ternary coordinate as answer: "The container is the 2nd from the bow, the 1st from port, 3rd stacking tier. There, in turn, it is the 7th box from the front, 6th from the left, 5th stacking tier." Without a tree data structure, the answer might have been: "9.43 m from the bow, 3.31m from port, 9.12 m above loading area", which in fact would be shorter, but more difficult to find.
Shifting in ternary coordinates: The captain corrects his answer: "Sorry, that was wrong. The box is one container more to the front and two crates farther to the right."
Zooming out: If the indication of the crate is enough for me, I will simply omit the part of the ternary coordinate relating to the box within the crate. Zooming in, accordingly, is the other way about.
Also subdivision of the world into country, town, street, house number, floor is a tree data structure, and the postal address is a ternary coordinate. In order not to violate the patent, postal addresses would have to be abolished and letters instead marked with, say, "50°43' northern latitude, 07°06' eastern longitude, 51.3m above sea level".

Examples for patent infringements: The claimed method for storing spatial data results, in a natural way, from the problem. It is thus very likely that numerous existing flight simulators and other programs working with spatial navigation violate this patent.

Previous Patent