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.
- US
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
painting order.
Patent 5123084 describes a similar nearest-first octree graphics method.
Patent
5222201 also concerns octree graphics methods, and describes
a heuristic for speeding up the conversion of objects into octree
representations.
- US
Patent 3889107 covers the use of binary space partitions for hidden
surface removal, shadow calculation, and collision detection.
- US
Patent 4704694 uses convex hulls to recognize objects from video images.
- US
Patent 4862373 is an early patent on robot motion planning
algorithms, referenced by many later patents on the same subject.
- US
Patent 4941114 covers an ear-cutting method of constructing
unstructured triangular meshes. Another meshing patent,
5214752,
describes an incremental point placement algorithm very similar to the
provably-good meshing method of one of its inventors (Jim Ruppert).
Patent
5440674 appears to be based on a very similar incremental method of Chew.
Meshing patents
4797842 and
4933889
are based on medial axes.
Patent
5315537 covers a wavefront-based quadrilateral meshing system.
Patent
5345490 covers quadtree- and octree-based meshing.
Patent
553206 describes methods of merging tetrahedra to simplify meshes.
- US
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.
- US
Patent 5086482 seems to cover gift-wrapping methods of computing convex hulls in bitmap images.
- US
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?
- US
Patent 5129051 covers a slab method of performing trapezoidal
decomposition and its application to scan-line conversion in computer graphics
(Patent
4791582).
Patent 5276783 is also on slab-based trapezoidalization.
Patent
5020002 is harder to
decode; it seems to be describing an ear-cutting trapezoidalization method.
- US Patents
5134480,
5228098,
5444489,
5446806,
5452104,
and
5469212
describe video and image coding methods based on quadtrees.
- US
Patent 5159645 performs character recognition by using convex hulls
to find the counters in each character. A similar idea also occurs in
Patent
4817166.
- US
Patent 5211692 covers a decorative tiling pattern based on the
geometry of zonohedra. Patents
5155951 and
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
5317681 and
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.
- US
Patent 5459831 covers the use of quadtrees to perform the range
queries needed for object selection in graphical user interfaces.
- US
Patent 5461712 uses quadtrees to allocate memory to different
objects in a windowing system.
- US
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
4888693,
4969110,
and
5053958
also use convex hulls for computerized tomography.
- US
Patent 5465221 describes a part inspection system including the use
of convex hulls to determine stable orientations.
- US
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.
- US
Patents
5506784,
5510994,
and
5541847
use medial axes to generate embroidery patterns.
- US
Patent 5564004 uses Voronoi diagrams as part of a user interface
that highlights the icon nearest the cursor in a windowing system.
- US
Patent 5574835 describes a method of performing visibility checking
of polygons by intersecting bounding boxes.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
