Patented Applications of Computational Geometry
Some of the following patents are applications of geometric algorithms,
while others appear to patent the algorithms themselves.
Presumably I have missed many more than I have found.
Patent 3602702 covers the quadtree subdivision of a viewing plane to perform hidden surface removal in computer graphics.
Patent 4694404 covers the use of octrees to implement a nearer-object-first
Patent 5123084 describes a similar nearest-first octree graphics method.
5222201 also concerns octree graphics methods, and describes
a heuristic for speeding up the conversion of objects into octree
Patent 3889107 covers the use of binary space partitions for hidden
surface removal, shadow calculation, and collision detection.
Patent 4704694 uses convex hulls to recognize objects from video images.
Patent 4862373 is an early patent on robot motion planning
algorithms, referenced by many later patents on the same subject.
Patent 4941114 covers an ear-cutting method of constructing
unstructured triangular meshes. Another meshing patent,
describes an incremental point placement algorithm very similar to the
provably-good meshing method of one of its inventors (Jim Ruppert).
5440674 appears to be based on a very similar incremental method of Chew.
are based on medial axes.
5315537 covers a wavefront-based quadrilateral meshing system.
5345490 covers quadtree- and octree-based meshing.
553206 describes methods of merging tetrahedra to simplify meshes.
Patent 5054098 describes a method of detecting whether a scanned
image has been turned at an angle from the original, using an algorithm
for finding minimum enclosing rectangles along with other techniques.
Patent 5086482 seems to cover gift-wrapping methods of computing convex hulls in bitmap images.
Patent 5115479 covers the compression of bitmap data by using spline
curves to represent the image outlines. Isn't that what standard font
formats already did?
Patent 5129051 covers a slab method of performing trapezoidal
decomposition and its application to scan-line conversion in computer graphics
Patent 5276783 is also on slab-based trapezoidalization.
5020002 is harder to
decode; it seems to be describing an ear-cutting trapezoidalization method.
- US Patents
describe video and image coding methods based on quadtrees.
Patent 5159645 performs character recognition by using convex hulls
to find the counters in each character. A similar idea also occurs in
Patent 5211692 covers a decorative tiling pattern based on the
geometry of zonohedra. Patents
5448868 cover similar three-dimensional building systems.
- US Patent 5268998 seems to cover graphical display of objects in non-Euclidean or higher dimensional geometries.
- US Patents
5428717 cover methods for finding convex hulls of
polyhedra based on flipping reflex edges, along with an animated version
of this procedure that creates a smooth morph of the polyhedron to its hull.
Patent 5459831 covers the use of quadtrees to perform the range
queries needed for object selection in graphical user interfaces.
Patent 5461712 uses quadtrees to allocate memory to different
objects in a windowing system.
Patent 5463721 describes the use of convex hulls in a method for finding a
path for a radiation-beam scanner so it can get enough data
to reconstruct object shapes. Patents
also use convex hulls for computerized tomography.
Patent 5465221 describes a part inspection system including the use
of convex hulls to determine stable orientations.
Patent 5483606 describes a method of registering (lining up) copied
pages with each other in a copying machine, using the convex hulls of
images of the pages.
use medial axes to generate embroidery patterns.
Patent 5564004 uses Voronoi diagrams as part of a user interface
that highlights the icon nearest the cursor in a windowing system.
Patent 5574835 describes a method of performing visibility checking
of polygons by intersecting bounding boxes.
Geometry in Action,
a collection of applications of computational geometry.
from a common source file.