NOVEL METHOD FOR THE FAST DERIVATION OF DELAUNAY TESSELATIONS
First Claim
1. A novel method for storing information in O(n log n) time and retrieving said data in constant time using a combined red-black tree/sorted linked list data structure such that insertions into the red-black tree/sorted linked list structure require the normal O(log n) but that retrieval of information from the red-black tree/sorted linked list structure requires only O(1) time.
0 Assignments
0 Petitions
Accused Products
Abstract
Three novel methods are provided which are valuable for the field of Delaunay tessellation derivation. The invention, implementable via various means such a digital processing system or an electronic circuit, has wide ranging applicability to numerous fields such as big data analysis, computer graphics and animation, mute planning, collision avoidance, computer vision, robotic vision, and etc. The first method of the invention details steps necessary to insert information into a data structuring in O(log n) while simultaneously retrieving sorted information relevant to the newly inserted information in O(1) time. The second method of the invention details and improvement to the Bowyer-Watson method that brings its runtime down to a tight O(n log n). The third method of the invention details steps necessary to compute the Delaunay tessellation of a set of line segment generators in k in O(n log n) time.
3 Citations
4 Claims
-
1. A novel method for storing information in O(n log n) time and retrieving said data in constant time using a combined red-black tree/sorted linked list data structure such that insertions into the red-black tree/sorted linked list structure require the normal O(log n) but that retrieval of information from the red-black tree/sorted linked list structure requires only O(1) time.
-
2. An improvement upon the Bowyer-Watson method for the derivation of Voronoi diagrams in Rk, where k≧
- 2;
whereby, a combined red-black tree/sorted linked list is utilized as a radial index such when a new generator is inserted into a subset S of generators participating in the worst-case scenario for the Bowyer-Watson method the insertion of the new generator into S still only requires O(log n) time;
thereby enabling the modified Bowyer-Watson method to have a tight O(n log n) runtime instead of a worst-case runtime of O(n2).
- 2;
-
3. The development of a novel, fast method for deriving Delaunay tessellations for sets containing line segments in, Rk, where k≧
- 2, that can be described as follows;
first, the Delaunay tessellation, DT, is computed for the set of endpoints for the set of line segment generators in O(n log n) time;
second, the Delaunay tessellation for the set of line segments generators is computed from DT in O(c12) time, where c is a factor proportional to the number of spheres with diameter equal to the length of the shortest line segment that can participate in the tightest packing of spheres around the longest line segment divided by 12, by scanning all edges in DT to see which line segments in DT share and edge;
- View Dependent Claims (4)
- 2, that can be described as follows;
Specification