List of Prior Art "Inventions" Claimed
by Kent Paul Dolan
for Intellectual Property Agreement Documents

Brief Name of Invention Rough Date of Invention "Witness" to Invention Abstract of Invention
visual chewing gum 1974 to 1984 Sent out as floppy disk sneakernet freeware to the world. Frequently seen as come-on displays in personal computer stores to this date. A series of about 22 visual displays of walking lines, moire fringe radial sweeps, plaid patch overlays, and other simple screen saver-style eye candy, run from a menu.
townmaze 1985 to 1988 Distributed as Internet freeware, currently available as townmaze version 1.4, in a compressed tarball format, on any of the aminet mirror sites. A dungeon crawl game city or maze layout tool that designs streets and rooms and city walls laid out on a grid in response to a large number of command line parameters. The invention in this is the connectivity algorithm, used to guarantee that all rooms are accessible exactly once from a street, and that most rooms are laid out back to back, and that, in the simplest default parameters case, the street network is a tree structured graph.
hexmaze 1987 to 1989 data file time stamps on floppy disks Designs and prints to screen or hardcopy or file, single-entrance, single-exit tree-connected hexagonal mazes expressed in ASCII text. Useful as a starting point for hand designed dungeon levels; the softcopy can be edited to clear out rooms within the maze for further dungeon design steps.
fast raster image rotator 1989 to 1991 data file time stamps on floppy disks Adoption of Bresenham's well known line drawing pixelization algorithm to two dimensions as a sampling tool for use in doing a full 2-D transformation (rotation, translation, and scaling) of rectangular raster image areas using only long integer arithmetic.
arithmetic compression of binary octet data to printable ASCII 1986 to 1989 data file time stamps on floppy disks Adaptation of arithmetic compression algorithm published in Communications of the ACM of about 1983, to compress arbitrary binary octet stream data to printable ASCII characters, thirteen bits of compressed data becoming two printable characters. This software was used to push data across a low speed communications link sensitive to the high octet bit being on in the data being transmitted.
arithmetic compression using heaps 1987 to 1994 data compressed with this tool ranging over several years; time stamps on the archive softcopies of the software source code The arithmetic compression published in Communications of the ACM used sliding most recently used to front character frequency bins. This invention replaced those moving bins with fixed location frequency bins managed by a heap with annotated nodes. This improves the worst case behavior of the compression algorithm and is easily extended to multiple byte compression mechanisms and efficient representation of consecutive empty bins.
text column setter 1995 to 1997 data file time stamps on floppy disks A tabular data columnizing tool for monospaced text that automatically sets various types of data with proper default justifications, adjusts the number of columns to the screen width, and intelligently adjusts individual column widths depending on the maximum width of the data falling in that column in a backtracking parser fashion to put the maximum number of columns on the display surface, and thus the minimum number of rows, in an attempt to show as much as possible of a data set at once in a screen space limited viewport into that data set.
fancy typesetting using a backtracking parser 1988 to 1991 data file time stamps on floppy disks Justification of kerned, variable width font text in mixed sizes and styles and colors and language and glyph types, with left, right, top, bottom justification per display surface rectangular text area boxes, flowed through a list of such boxes.
greedy heuristic maximal packing of data files to multiple heterogeneously sized storage media 1991 to 1994, 1999 US Navy has the original C language source code, written based on earlier art to create software and data distribution floppy diskette kits. I recently reimplemented this tool from scratch in the Perl5 programming language for personal use. Application of the computer science theoretic greedy algorithm heuristic solution for knapsack packing, of many files to many homogeneous or hetrogeneous storage media. The most recent implementation contains added intelligence to avoid the effects of the long existing bug in the Unix mtools software that causes occasional but replicable failures when a floppy disk and the current directory block on that disk fill up at the same time. It is capable of efficiently storing thousands of files on hundreds of floppy disks, with low computational overhead for planning the knapsack layout of the entities.
mixed tool surveying using radio location and sextant measurements 1974 to 1976 The original survey method description, associated software and that software's documentation are in the custody of the United States Department of Commerce, National Oceanic and Atmospheric Administration Commissioned Corps, where all was published as an internal report. This survey method and associated software solves the problem of locating inaccessible land objects accurately from a moving survey launch using Raydist(TM) radio navigation and a hand held sextant. It was used to determine the position of the north navigation light (sited on a dangerous and narrow hogback mountain ridge) on Santa Catalina Island, California, USA, during the regularly scheduled 30 year hydrographic resurvey of the surrounding water and land.
accurate fixes by theodolite resection 1975 The original survey method description, associated software and that software's documentation are in the custody of the United States Department of Commerce, National Oceanic and Atmospheric Administration Commissioned Corps, where all was published as an internal report. Resection, surveying outward from the site whose location is desired to be determined rather than inward from known locations looking toward the site, is so weak a survey technique that it is ordinarily rejected without further thought. Given sufficient objects of known location, however, it is fully capable of providing a robust and accurate location for the central object. This method was invented, and software to implement it written (for a Wang Desktop Programmable Calculator) to solve a one of a kind survey requirement for a floating platform in mid-harbor where ground transportation to the surrounding already surveyed sites was not readily available. The resulting fix provided a location with one meter circular error expectation.
rapid rasterization of fat lines from vector data, with applications to cartography publishing needs 1976 to 1979 The original software and that software's documentation are in the custody of the United States Department of Commerce, National Oceanic and Atmospheric Administration Commissioned Corps, where it is probably still in daily use. This invention provided a $10,000,000 cost avoidance for the US DoC over the expected application lifetime, by reducing a more naive vendor implementation's runtime by a factor of 12. The inventions claimed are breaking the vectors to berendered as pixels into very short pieces accurately following the original line, conceptually capping the ends of those short pieces with semi-disks so that corners could be turned smoothly with adjacent short pieces, and pre-computing the raster images of those short vectors into tables stored in memory at executable module load time, from which they could be fetched by fast table lookup, rather than doing the more computationally expensive needed point in polygon and point in circle computations, at run time.
robust point in "multiply intersecting or multiply nested" polygons classification 1976 to 1979 The original software and that software's documentation are in the custody of the United States Department of Commerce, National Oceanic and Atmospheric Administration Commissioned Corps, where it is probably still in daily use. The usual count polygon border intersections of a ray from the point to be classified to infinity algorithm suffers in naive implementations from failures when the ray exactly intersects a polygon vertex where two intersections would be counted but only one intersection appropriately counted, or when the ray is coincident for part of its length with one of the polygon's edges. There are many solutions in the literature for this problem, the one claimed here seems to have been overlooked:
  • make the polygon edges one dimensional space intervals open on exactly the downward pointing end and closed on the other end;
  • ignore ray intersections with horizontal polygon edges altogether.
The result was a routine that allowed clean creation of small point sized text glyphs, and that supported the short vector rasterization of the previous listed invention. This mechanism makes the classification independent of the connectivity of the polygon edges, allowing the edges to be disassembled and sorted before running a scan line algorithm. This can make a profound speed improvement by limiting the number of edges that must be consulted for a single scan line. Further improvements by computing and sorting the intersections of the sorted polygon edges with the scan line allow classification of pixels in groups of run lengths between intersections, rather than one by one.
satellite cellular phone satellite to satellite and groundstation to groundstation handoff physics and control traffice simulation, with applications to minimizing control traffic overhead and satellite battery drain 1995 to 1996
co-inventer
Original software is in the custody of Qualcomm(tm). Various unique algorithms used to account for physical radio multipath interference and meteorological attenuation causes of signal strength variations and need for handoff are claimed. Various unique algorithms to choose "the best" from a variety of available satellites above the horizon and associated co-visible groundstations so as to minimize handoff needs, based in part on call duration statistics per customer or customer class, in part on ordinary or premium service classes, and in part on simulation of satellite solar energy capture, satellite battery use, and satellite total call traffic, are claimed.
three dimensional, four-in-a-row tic-tac-toe, using neural net learning mechanisms 1965 to 1987 Copies exist on backup media dating back to the original implementation as a college programming exercise. As an exercise in understanding the programming of neural nets, I created software to play, interactively against a human, or, in batch mode with the software playing against itself, the common paper and pencil 4x4x4 tic-tac-toe game of my high school years. The software has the following "invented" characteristics.
  • It is non-deterministic. Not the one best play, but a random play among the top three ranking plays is chosen unless that would result in an immediate win for the opponent.
  • It is self-taught. It starts out particularly awful, since it has almost no prebuilt playing strategy knowledge, and learns from analyzing both its successes and its failures, putting the analysis results to use by typical neural net link re-enforcement techniques, and grows progressively better with play, becoming challenging after about a hundred games of experience, and eventually always besting the strongest human opponent after playing a thousand games or so.
  • It implements persistent learning: it can be directed to save and restore its lists of link weights to and from disk files (originally, to and from punched card decks).
  • It does not in any sense come to a closed form solution: there is probably a known forced win for this simple game for either the first or the second player. Techniques known for 2-D tic-tac-toe to arrive at a best "always draws" solution were deliberately avoided in this implementation.
  • It is its own strategist. Except for avoiding an immediate loss or taking an immediate win, there is no implementor provided strategy for the game at all, primarily because a way to force a win, or even a good strategy for play, were unknown to this implementor then, and still are now.
A genetic algorithm permutation genome crossover method implemented in the Java programming language called GaussianCrossover. 2001 to 2003 Frequent announcements in Usenet's comp.ai.genetic, comp.lang.java.programmer; staged publication on my account at The Well here, use of results to create TravellerArt linked from here. Two parent genomes expressed as arrays containing permutations of the integers 0 to (N-1) are placed in general position with respect to one another. The distance between like allele indices, plus unity, between the two parents is called the span; based on a tuning parameter, from the center of this span, it's two edges are matched to points on the positive and negative parts of a Gaussian normal curve as a scaling mechanism for that normal curve. A random real number with Gaussian distribution, centered on the span center and scaled by the tuning parameter is then assigned to the allele's name. When all allele names have such an assignment, the allele names are then sorted in the order of the assigned random number. This sorted list becomes the child permutation genome.
A genetic algorithm permutation genome crossover method implemented in the Java programming language called RollingCrossover. 2001 to 2003 Frequent announcements in Usenet's comp.ai.genetic, comp.lang.java.programmer; staged publication on my account at The Well here, use of results to create TravellerArt linked from here. Two parent genomes expressed as arrays containing permutations of the integers 0 to (N-1) are placed in general position with respect to one another. Walking the parent genomes in order, note is taken whenever the lists of encountered allele names for each parent contain the same sets of names. At each such point, the list of alleles since the last such synchronizition from the parent which would provide the better incremental fitness is copied to the child genome.
A genetic algorithm permutation genome crossover method implemented in the Java programming language called EdgePreservingCrossover. 2001 to 2003 Frequent announcements in Usenet's comp.ai.genetic, comp.lang.java.programmer; staged publication on my account at The Well here, use of results to create TravellerArt linked from here. In the permutation genome, a consecutive pair of allele names in the genome considered as a mathematical ring is treated as an edge. Lists of edges which occur in both parent genomes are accumulated. One or more edges which occur in the same order, or as a list in fully reversed order, in both parents, or isolated alleles not part of a doubly occuring edge, are treated as a bin. Bins are crossed over using the same mechanism used for alleles in the classical Cyclic Crossover which is part of the existing art for permutation genomes. Then, within constraints of computation complexity limitation for an essentially exponential process, reversals of the bins with more than one allele are done until one with best encountered fitness is chosen. The bins in this order are then unpacked back into a permutation genome.

This page, maintained by
Kent Paul Dolan
xanthian@well.com ,  
was last updated
20030221.