# US 2015/0106392 A1 · Planar graph generation device and method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0106392 A1
- Document ID: US20150106392A1
- Status: Published application
- Kind: A1
- Application number: 14/510,223
- Filed: 2014-10-09
- Published: 2015-04-16
- Earliest claimed: 2013-10-11
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Hiroya INAKOSHI; Tatsuya Asai; Hiroaki Morikawa; Junichi Shigezumi
- Web page: https://patentgrep.com/patent/US20150106392A1

## CPC

- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A planar graph generation device that includes a processor that executes a process. The process includes: computing a specific value, including components of a value representing complexity of a track of the given track data, and a value representing a non-nearness between the given track data and each of all the other track data; selecting the track data with the smallest specific value among the collection; a first portion of the first track or a second portion of the second track positioned within the specific distance of each other, or a combination of the first portion and the second portion, is approximated to a specific portion such that a track of the addition target track data after addition passes through the specific portion in cases in which there are portions positioned within the specific distance of each other in a combination of the first track with the second track.

## Claims

### Claim 1

A planar graph generation device comprising:
a memory; and
a processor configured to execute a process, the process comprising:
in a collection of track data, each representing a track along which a moving body has moved, transitioning processing to another track data at each processing time, and for each given track data in the collection, computing a specific value, including components of a value representing complexity of a track of the given track data, and a value representing a non-nearness between the given track data and each of all the other track data in the collection other than the given track data;
selecting the track data with the smallest specific value among the collection;
based on the selected track data and on addition target track data that is a target of addition, generating addition target track data after addition such that the selected track data is added to the addition target track data in cases in which there are no portions positioned within a specific distance of each other in any combination of the selected track data as a first track and each respective track of the addition target track data as a second track, and such that a first portion of the first track or a second portion of the second track positioned within the specific distance of each other, or a combination of the first portion and the second portion, is approximated to a specific portion such that a track of the addition target track data after addition passes through the specific portion in cases in which there are portions positioned within the specific distance of each other in a combination of the first track with the second track; and
executing, for all track data in the collection, computation of the specific value, selection of track data having the smallest specific value, and generation of the addition target track data after addition.

### Claim 2 (depends on 1)

The planar graph generation device of claim 1, the process further comprising:
determining whether or not there is track data remaining in the collection, and whether or not the computed specific value has fallen below a previous specific value; and
in cases in which it is determined that there is track data in the collection and the computed specific value has not fallen below the previous specific value, adding all the track data remaining in the collection to the addition target track data during generation of the addition target track data after addition.

### Claim 3 (depends on 1)

The planar graph generation device of claim 1, wherein computing the specific value includes determining whether or not there are portions positioned within a specific distance of each other in a combination of the track of the given track data and each respective track of all the other track data, the value representing the non-nearness being computed based on content of track data of portions other than the portions positioned within the specific distance of each other in cases in which there are portions positioned within the specific distance of each other in the respective tracks, and the value representing the non-nearness being computed based on content of the given track data and content of each of all the other track data in cases in which there are no portions positioned within the specific distance of each other in the respective tracks.

### Claim 4 (depends on 1)

The planar graph generation device of claim 1, wherein
the specific value is a summation value of the value representing the complexity and the value representing the non-nearness.

### Claim 5 (depends on 4)

The planar graph generation device of claim 4, wherein
the summation value is a weighted summation value.

### Claim 6 (depends on 1)

The planar graph generation device of claim 1, wherein:
the given track data includes a plurality of positional data each representing a position on a track along which the moving body has moved and link data representing links between positions; and
the value representing the complexity of the track is expressed by at least one selected from the group consisting of a number of positions expressed by the positional data, a number of the links, and a total length of the links.

### Claim 7 (depends on 1)

The planar graph generation device of claim 1, wherein:
the given track data include a plurality of positional data each representing a position on a track along which the moving body has moved and link data representing links between positions; and
the value representing the non-nearness is expressed by at least one selected from the group consisting of the number of positions of portions in the respective tracks of the given track data and the other track data other than in portions positioned within a specific distance of each other, the number of links therein, the total length of the links therein, a surface area determined from the positions and the links therein, and a greatest distance between the positions therein.

### Claim 8 (depends on 6)

The planar graph generation device of claim 6, wherein
the value representing the non-nearness is expressed by at least one selected from the group consisting of the number of positions of portions in the respective tracks of the given track data and the other track data other than in portions positioned within a specific distance of each other, the number of links therein, the total length of the links therein, a surface area determined from the positions and the links therein, and a greatest distance between the positions therein.

### Claim 9

A non-transitory recording medium storing a program that causes a computer to execute a planar graph generation process, the process comprising:
in a collection of track data, each representing a track along which a moving body has moved, transitioning processing to another track data at each processing time, and for each given track data in the collection, computing a specific value, including components of a value representing complexity of a track of the given track data, and a value representing a non-nearness between the given track data and each of all the other track data in the collection other than the given track data;
selecting the track data with the smallest specific value among the collection;
based on the selected track data and on addition target track data that is a target of addition, generating addition target track data after addition such that the selected track data is added to the addition target track data in cases in which there are no portions positioned within a specific distance of each other in any combination of the selected track data as a first track and each respective track of the addition target track data as a second track, and such that a first portion of the first track or a second portion of the second track positioned within the specific distance of each other, or a combination of the first portion and the second portion, is approximated to a specific portion such that a track of the addition target track data after addition passes through the specific portion in cases in which there are portions positioned within the specific distance of each other in a combination of the first track with the second track; and
executing, for all track data in the collection, computation of the specific value, selection of track data having the smallest specific value, and generation of the addition target track data after addition.

### Claim 10 (depends on 9)

The non-transitory recording medium of claim 9, the planar graph generation process further comprising:
determining whether or not there is track data remaining in the collection, and whether or not the computed specific value has fallen below a previous specific value; and
in cases in which it is determined that there is track data in the collection and the computed specific value has not fallen below the previous specific value, adding all the track data remaining in the collection to the addition target track data during generation of the addition target track data after addition.

### Claim 11 (depends on 9)

The non-transitory recording medium of claim 9, wherein, in the planar graph generation process:
computing the specific value includes determining whether or not there are portions positioned within a specific distance of each other in a combination of the track of the given track data and each respective track of all the other track data, the value representing the non-nearness being computed based on content of track data of portions other than the portions positioned within the specific distance of each other in cases in which there are portions positioned within the specific distance of each other in the respective tracks, and the value representing the non-nearness being computed based on content of the given track data and content of each of all the other track data in cases in which there are no portions positioned within the specific distance of each other in the respective tracks.

### Claim 12 (depends on 9)

The non-transitory recording medium of claim 9, wherein, in the planar graph generation process, the specific value is a summation value of the value representing the complexity and the value representing the non-nearness.

### Claim 13 (depends on 12)

The non-transitory recording medium of claim 12, wherein, in the planar graph generation process, the summation value is a weighted summation value.

### Claim 14 (depends on 9)

The non-transitory recording medium of claim 9, wherein, in the planar graph generation process:
the given track data includes a plurality of positional data each representing a position on a track along which the moving body has moved, and link data representing links between positions; and
the value representing the complexity of the track is expressed by at least one selected from the group consisting of a number of positions expressed by the positional data, a number of the links, and a total length of the links.

### Claim 15 (depends on 9)

The non-transitory recording medium of claim 9, wherein, in the planar graph generation process:
the given track data include a plurality of positional data each representing a position on a track along which the moving body has moved, and link data representing links between positions; and
the value representing the non-nearness is expressed by at least one selected from the group consisting of the number of positions of portions in the respective tracks of the given track data and the other track data other than in portions positioned within a specific distance of each other, the number of links therein, the total length of the links therein, a surface area determined from the positions and the links therein, and a greatest distance between the positions therein.

### Claim 16 (depends on 14)

The non-transitory recording medium of claim 14, wherein, in the planar graph generation process:
the value representing the non-nearness is expressed by at least one selected from the group consisting of the number of positions of portions in the respective tracks of the given track data and the other track data other than in portions positioned within a specific distance of each other, the number of links therein, the total length of the links therein, a surface area determined from the positions and the links therein, and a greatest distance between the positions therein.

### Claim 17

A planar graph generation method comprising:
in a collection of track data, each representing a track along which a moving body has moved, transitioning processing to another track data at each processing time, and for each given track data in the collection, computing a specific value, including components of a value representing complexity of a track of the given track data, and a value representing a non-nearness between the given track data and each of all the other track data in the collection other than the given track data;
selecting the track data with the smallest specific value among the collection;
by a processor, based on the selected track data and on addition target track data that is a target of addition, generating addition target track data after addition such that the selected track data is added to the addition target track data in cases in which there are no portions positioned within a specific distance of each other in any combination of the selected track data as a first track and each respective track of the addition target track data as a second track, and such that a first portion of the first track or a second portion of the second track positioned within the specific distance of each other, or a combination of the first portion and the second portion, is approximated to a specific portion such that a track of the addition target track data after addition passes through the specific portion in cases in which there are portions positioned within the specific distance of each other in a combination of the first track with the second track; and
executing, for all track data in the collection, computation of the specific value, selection of track data having the smallest specific value, and generation of the addition target track data after addition.

### Claim 18 (depends on 17)

The planar graph generation method of claim 17, further comprising:
determining whether or not there is track data remaining in the collection, and whether or not the computed specific value has fallen below a previous specific value; and
in cases in which it is determined that there is track data in the collection and the computed specific value has not fallen below the previous specific value, adding all the track data remaining in the collection to the addition target track data during generation of the addition target track data after addition.

### Claim 19 (depends on 17)

The planar graph generation method of claim 17, wherein:
computing the specific value includes determining whether or not there are portions positioned within a specific distance of each other in a combination of the track of the given track data and each respective track of all the other track data, the value representing the non-nearness being computed based on content of track data of portions other than the portions positioned within the specific distance of each other in cases in which there are portions positioned within the specific distance of each other in the respective tracks, and the value representing the non-nearness being computed based on content of the given track data and content of each of all the other track data in cases in which there are no portions positioned within the specific distance of each other in the respective tracks.

### Claim 20 (depends on 17)

The planar graph generation method of claim 17, wherein the specific value is a summation value of the value representing the complexity and the value representing the non-nearness.
