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

• US 8,050,689 B2
• Filed: 12/13/2005
• Issued: 11/01/2011
• 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
• Primary Examiner(s): DOAN, PHUOC HUU
• Application Number:
  US11/314,187
• Publication Number:
  US 20070146374A1
• Time in Patent Office: 2,149 Days
• Field of Search: 455/456.1, 382/113, 701/211, 701/209
• US Class Current: 455/456.1
• 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 system-implemented method determining a minimum bounding polygon for use in a geo-coding system, the method comprising:

receiving, by a processor, a first polygon defining a first geographic region;

receiving, by a processor, a second polygon defining a second geographic region;

receiving, by a processor, 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 the second geographic region defined by the second polygon; and

determining, by a processor, a minimal number points corresponding to the first and second polygons to define a third polygon at least bounding the first and second polygon, wherein the number of points determined is based on the accuracy specification.

2. 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;

receive a second polygon defining a second geographic region;

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 the second geographic region defined by the second polygon; 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, wherein the number of points determined is based on the accuracy specification.

3. 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, a second polygon defining a second geographic region, and 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 the second geographic region defined by the second polygon; and

means, coupled with the means for receiving, for determining a minimal number of points corresponding to the first and second polygons to define a third polygon at least bounding the first and second polygons, wherein the number of points determined is based on the accuracy specification.

4. 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 and a received second polygon defining a second 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 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 the second geographic region defined by the second polygon; and

second logic operative to determine a minimal number of points corresponding to the first and second polygons to define a third polygon at least bounding the first and second polygons, wherein the number of points determined is based on the accuracy specification.