Patent ID: 8442805
Filing Date: 2013-05-14
Classification: G06K,G06T

Abstract:
1. A computerized method of decomposing a given region X into cells, the decomposition being induced by a set of generators (P k ) k - K , and a distance function by finding for each generator P k a cell, the cell comprising a set of all the points in X satisfying a distance inequality condition based on said distance function that the distance to a current generator P=P k is not greater than the distance thereof to the union A of the other generators, the method being carried out on an electronic processor and comprising: for each generator, and for each point p in this generator, selecting a plurality of directions and for each direction recursively testing a ray in the direction, for intervals along the ray until a predetermined stopping condition is reached, wherein said recursively testing comprises bisecting the ray into two intervals to provide a middle point y, and then testing said distance inequality condition at y, and according to the result, selecting either the interval prior to the point y or beyond the point y for further bisection and testing, and wherein said stopping condition comprises a determination that the length of the corresponding interval is less than or equal to a further predetermined error parameter; selecting a point corresponding to the interval as an end point, and storing the end point in a machine readable format; defining at least one cell from said end points, thereby decomposing said region X; outputting said decomposed region X comprising said at least one cell in machine readable format; and applying said decomposed region to one member of the group comprising: controlling a communications network, managing a communication network, controlling a robot, managing a robot, modeling, testing or simulating a three-dimensional network, controlling a three-dimensional network, testing or modeling a material, data searching, searching for data on a network or database, image processing, mesh generation and re-meshing, curve and surface generation, curve and surface reconstruction, solid modeling, collision detection, controling motion of vehicles, navigation, accident prevention, data clustering and data processing, proximity operations, nearest neighbor search, numerical simulations, weather prediction, analyzing or modeling proteins, analyzing or modeling biological structures, designing drugs, finding shortest paths, pattern recognition, rendering, data compression, providing overall control of a plurality of methods for image processing, providing overall control of a plurality of methods for data categorization, providing overall control for a plurality of methods for data clustering, designing and testing of electronic circuits, management of geographic information systems, locating a resource according to the solution of an efficient location problem, face recognition, and an artistic tool.