Cost zones

Claim 3

A method according to claim 1, further including the step of connecting said locations.

Claim 4

A method according to claim 1, wherein: said desired cost is a traveling time.

Claim 5

A method according to claim 1, wherein: said desired cost is a distance.

Claim 6

A method according to claim 1, wherein: said desired cost is a cost of traveling away from said origin.

Claim 7

A method according to claim 1, wherein: said desired cost is a cost of traveling toward said origin.

Claim 8

A method according to claim 1, wherein: said step of triangulating includes creating Delaunay triangles.

Claim 9

A method according to claim 1, wherein: each of said sides of said triangles have two end points, both end points being nodes; and said step of interpolating includes the steps of: finding one of said sides having one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost; interpolating along said one side to find a first location along said one side having a cost equal to said desired cost; choosing a triangle that includes said one side; choosing a next side of said chosen triangle, said next side not being said one side, said next side including one end point with a cost less than said desired cost and a second end point having a cost greater than said desired costs; and interpolating along said next side to find a second location along said next side having a cost equal to said desired cost.

Claim 10

A method according to claim 1, further including the step of: determining an island inside said cost zone, said island representing an area not accessible within said desired cost.

Claim 11

A method according to claim 1, further including the step of: determining an island outside said cost zone, said island representing an area accessible within said desired cost.

Claim 12

A method according to claim 1, further including the step of: symbolically connecting said locations.

Claim 13

A method according to claim 1, further including the step of: storing a list of said locations in a computer readable storage medium.

Claim 14

A method according to claim 2, wherein: said list stores latitude and longitude data for said locations.

Claim 15

A method according to claim 1, wherein: said step of identifying a set of nodes includes the steps of: a) considering said origin as a head node of a priority queue; b) determining, for each neighbor node of said head node, a travel cost of traveling from said origin, through said head node, to said neighbor node; c) storing in said priority queue each neighbor node of said head node and said travel cost, if said neighbor node is not already stored in said queue with a lower travel cost; and d) removing said head node from said queue such that said queue has a new head node.

Claim 16

A method according to claim 14, further including the step of e) repeating steps b)-d) if said new head node's travel cost stored in said queue is less than said predetermined factor of said desired cost.

Claim 17

A method according to claim 1, wherein: said step of triangulating includes the steps of: (a) adding three nodes to a data structure; (b) creating a triangle out of said three nodes; (c) adding an additional node to said data structure; (d) connecting all three vertices of a surrounding triangle to said additional node, if said additional node is within said surrounding triangle; (e) connecting said additional node to all nodes in said data structure that said additional node can be connected to by a straight line without intersecting any sides of triangle if said additional node is not within any triangles; (f) connecting said additional node to a vertex opposite a particular side of a particular triangle, if said additional node is on said particular side; and (g) determining whether at least a subset of triangles represented in said data structure are Delaunay triangles.

Claim 18

A method according to claim 16, wherein: repeating steps (c)-(g) until all additional nodes have been added to said data structure.

Claim 19

A method according to claim 1, wherein: said step of interpolating includes: interpolating along a first side of a first triangle, said first side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost; interpolating along a second side of a second triangle, said second side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said second triangle sharing said first side with said first triangle; and interpolating along a third side of a third triangle, said third side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said third triangle sharing said second side with said second triangle.

Claim 20

A method according to claim 18, wherein: said step of interpolating along a first side determines a first interpolated location; said step of interpolating along a second side determines a second interpolated location; said step of interpolating along a third side determines a third interpolated location; and said method further includes the steps of connecting said first interpolated location with said second interpolated location, and connecting said second interpolated location with said third interpolated location.

Claim 21

A computer readable storage medium having computer readable code embodied on said computer readable storage medium, said computer readable code for creating a cost zone, said computer readable code comprising: first program code, said first program code identifies a set of nodes on an electronic map that are within a predetermined factor of a desired cost of an origin; second program code, said second program code triangulates said set of nodes to create a set of triangles, said triangles having sides; and third program code, said third program code interpolates along a subset of said sides of said triangles to estimate locations on said sides having said desired cost, said locations defining a boundary of said cost zone.

Claim 22

A computer readable storage medium having computer readable code embodied on said computer readable storage medium, said computer readable code for creating a cost zone, said computer readable code comprising: first program code, said first program code identifies a set of nodes on an electronic map that are within a predetermined factor of a desired cost of an origin; second program code, said second program code triangulates said set of nodes to create a set of triangles, said triangles having sides; and third program code, said third program code interpolates along a subset of said sides of said triangles to estimate locations on said sides having said desired cost, said locations defining a boundary of said cost zone.

Claim 23

A computer readable storage medium according to claim 20, wherein said computer readable code further comprises: fourth program code, said fourth program code stores a list of said locations in a computer readable storage medium, said list stores latitude and longitude data for said locations.

Claim 24

A computer readable storage medium according to claim 20, wherein: said second program code creates Delaunay triangles.

Claim 25

A computer readable storage medium according to claim 20, wherein: said second program code: adds three nodes to a data structure; creates a triangle out of said three nodes; adds an additional node to said data structure; connects all three vertices of a surrounding triangle to said additional node, if said additional node is within said surrounding triangle; connects said additional node to all nodes in said data structure that said additional node can be connected to by a straight line without intersecting any sides of triangle if said additional node is not within any triangles; connects said additional node to a vertex opposite a particular side of a particular triangle, if said additional node is on said particular side; and determines whether a subset of said triangles in said data structure is a Delaunay triangle.

Claim 26

A computer readable storage medium according to claim 20, wherein: said third program code: interpolates along a first side of a first triangle, said first side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost; interpolates along a second side of a second triangle, said second side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said second triangle sharing said first side with said first triangle; and interpolates along a third side of a third triangle, said third side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said third triangle sharing said second side with said second triangle.

Claim 27

A computer readable storage medium according to claim 20, wherein: each of said sides of said triangles have two end points, both end points being nodes; and said third program code: finds one of said sides having one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost; interpolates along said one side to find a first location along said one side having a cost equal to said desired cost; chooses a triangle that includes said one side; chooses a next side of said chosen triangle, said next side not being said one side, said next side including one end point with a cost less than said desired cost and a second end point having a cost greater than said desired costs; and interpolates along said next side to find a second location along said next side having a third cost equal to said desired cost.

Claim 28

A computer readable storage medium according to claim 20, wherein: said first program code: a) considers said origin as a head node of a priority queue; b) determines for each neighbor node of said head node, a travel cost of traveling from said origin, through said head node and to said neighbor node; c) stores in said priority queue each neighbor node of said head node and said travel cost, if said neighbor node is not already stored in said queue with a lower travel cost; and d) removes said head node from said queue such that said queue has a new head node.

Claim 29

A computer readable storage medium according to claim 26, wherein: said first program code: e) repeats steps b)-d) if said new head node's travel cost stored in said queue is less than said predetermined factor of said desired cost.

Claim 32

An apparatus according to claim 28, wherein: each of said sides of said triangles have two end points, both end points having a first cost associated with traveling from said origin to node; and said means for interpolating includes: means for interpolating along a fast side of a first triangle, said first side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost; means for interpolating along a second side of a second triangle, said second side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said second triangle sharing said first side with said first triangle; and means for interpolating along a third side of a third triangle, said third side including one end point having a cost less than said desired cost and a second end point having a cost greater than said desired cost, said third triangle sharing said second side with said second triangle.