System and method for creating minimum bounding rectangles for use in a geo-coding system

• US 20070146374A1
• Filed: 12/13/2005
• Published: 06/28/2007
• Est. Priority Date: 12/13/2005
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Riise, Sorren, Patel, Dev
• Granted Patent: US 8,050,689 B2
• Time in Patent Office: Days
• US Class Current: 345/505
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A method is disclosed for determining a minimum bounding polygon for use in a geo-coding system. A first polygon is received defining a geographic region. A minimal number of points is determined corresponding to the first polygon to define a second polygon at least bounding the first polygon.

Claims

1. A method determining a minimum bounding polygon for use in a geo-coding system, the method comprising:

receiving a first polygon defining a first geographic region; and

determining a minimal number of points corresponding to the first polygon to define a second polygon at least bounding the first polygon.

2. The method of claim 1, further comprising:

receiving an accuracy specification specifying a desired accuracy for determining other geographic regions one of adjacent to, proximate to, overlapping with, within or encompassed by the first geographic region defined by the first polygon; and

wherein the number of points determined is based on the accuracy specification.

3. The method of claim 1, wherein the receiving further comprises receiving a second polygon defining a second geographic region;

and

determining a minimal number points corresponding to the first and second polygons to define a third polygon at least bounding the first and second polygons.

4. The method of claim 3, further comprising:

receiving an accuracy specification specifying a desired accuracy for determining other geographic regions one of adjacent to, proximate to, overlapping with, within or encompassed by the first and second geographic regions defined by the first and second polygons; and

wherein the number of points determined is based on the accuracy specification.

5. A system for determining a minimum bounding polygon for use in a geo-coding system, based on a received first polygon defining a first geographic region, the system comprising:

a determining processor operative to determine a minimal number of points corresponding to the first polygon to define a second polygon at least bounding the first polygon.

6. The system of claim 5, wherein the determining processor is further operative to receive an accuracy specification specifying a desired accuracy for determining other geographic regions one of adjacent to, proximate to, overlapping with, within or encompassed by the first geographic region defined by the first polygon;

and wherein the number of points determined is based on the accuracy specification.

7. The system of claim 5, wherein the determining processor is further operative to receive a second polygon defining a second geographic region and determine a minimal number points corresponding to the first and second polygons to define a third polygon at least bounding the first and second polygons.

8. The system of claim 7, wherein the determining processor is further operative to receive an accuracy specification specifying a desired accuracy for determining other geographic regions one of adjacent to, proximate to, overlapping with, within or encompassed by the first and second geographic regions defined by the first and second polygons;

and wherein the number of points determined is based on the accuracy specification.

9. A system for determining a minimum bounding polygon for use in a geo-coding system, the system comprising:

means for receiving a first polygon defining a first geographic region; and

means, coupled with the means for receiving, for determining a minimal number of points corresponding to the first polygon to define a second polygon at least bounding the first polygon.

10. A system for determining a minimum bounding polygon for use in a geo-coding system, based on a received first polygon defining a first geographic region, the system comprising computer programming logic stored in a memory and executable by a processor coupled with the memory, the computer programming logic comprising:

first logic operative to determine a minimal number of points corresponding to the first polygon to define a second polygon at least bounding the first polygon.