[go: up one dir, main page]

WO2009002020A3 - Method and system for finding nearest neighbors based on vboronoi diagram - Google Patents

Method and system for finding nearest neighbors based on vboronoi diagram Download PDF

Info

Publication number
WO2009002020A3
WO2009002020A3 PCT/KR2008/002920 KR2008002920W WO2009002020A3 WO 2009002020 A3 WO2009002020 A3 WO 2009002020A3 KR 2008002920 W KR2008002920 W KR 2008002920W WO 2009002020 A3 WO2009002020 A3 WO 2009002020A3
Authority
WO
WIPO (PCT)
Prior art keywords
nearest neighbors
diagram
minimum distance
vboronoi
neighbors based
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/KR2008/002920
Other languages
French (fr)
Other versions
WO2009002020A2 (en
Inventor
Jae Woo Chang
Jung Ho Um
Yeon Jung Kim
Tae Hun Lee
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Industry Academic Cooperation Foundation of Chonbuk National University
Thinkware Systems Corp
Original Assignee
Industry Academic Cooperation Foundation of Chonbuk National University
Thinkware Systems Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Industry Academic Cooperation Foundation of Chonbuk National University, Thinkware Systems Corp filed Critical Industry Academic Cooperation Foundation of Chonbuk National University
Publication of WO2009002020A2 publication Critical patent/WO2009002020A2/en
Publication of WO2009002020A3 publication Critical patent/WO2009002020A3/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G01C21/36—Input/output arrangements for on-board computers
    • G01C21/3679—Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G—PHYSICS
    • G08—SIGNALLING
    • G08G—TRAFFIC CONTROL SYSTEMS
    • G08G1/00—Traffic control systems for road vehicles
    • G08G1/09—Arrangements for giving variable traffic instructions
    • G08G1/0962—Arrangements for giving variable traffic instructions having an indicator mounted inside the vehicle, e.g. giving voice messages
    • G08G1/0968—Systems involving transmission of navigation instructions to the vehicle

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Automation & Control Theory (AREA)
  • Navigation (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

Disclosed are a method and system for finding nearest neighbors based on a Voronoi diagram. The method includes maintaining boundary minimum distance information including a minimum distance matrix between boundary points of Voronoi cells, in an entire road network adopting the Voronoi diagram, retrieving a predetermined number of nearest neighbors corresponding to an arbitrary query point using the boundary minimum distance information, and providing a POI corresponding to the retrieved nearest neighbors with respect to the query point.
PCT/KR2008/002920 2007-06-26 2008-05-26 Method and system for finding nearest neighbors based on vboronoi diagram Ceased WO2009002020A2 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR1020070063023A KR100906313B1 (en) 2007-06-26 2007-06-26 Nearest point search method and system based on Voronoi diagram
KR10-2007-0063023 2007-06-26

Publications (2)

Publication Number Publication Date
WO2009002020A2 WO2009002020A2 (en) 2008-12-31
WO2009002020A3 true WO2009002020A3 (en) 2009-02-19

Family

ID=40186137

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/KR2008/002920 Ceased WO2009002020A2 (en) 2007-06-26 2008-05-26 Method and system for finding nearest neighbors based on vboronoi diagram

Country Status (2)

Country Link
KR (1) KR100906313B1 (en)
WO (1) WO2009002020A2 (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109253717A (en) * 2018-10-09 2019-01-22 安徽大学 A kind of mining area surface sedimentation 3 D laser scanning surface subsidence monitoring sets station method

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101040521B1 (en) * 2009-10-13 2011-06-16 한국기술교육대학교 산학협력단 Urban-based Sensing Range Expansion Method of Moving Objects with Sensors
WO2011162423A1 (en) * 2010-06-22 2011-12-29 전북대학교산학협력단 Method and system for finding nearest neighbor using voronoi diagram
KR101678939B1 (en) * 2010-08-12 2016-11-23 팅크웨어(주) Apparatus and method for searching around
JP4777476B1 (en) * 2010-08-31 2011-09-21 株式会社東芝 Electronic map data processing system
CN102253961A (en) * 2011-05-17 2011-11-23 复旦大学 Method for querying road network k aggregation nearest neighboring node based on Voronoi graph
KR101421671B1 (en) * 2012-07-12 2014-07-22 아주대학교산학협력단 A DISTRIBUTED METHOD FOR CONTINUOUS MONITORING OF CONSTRAINED k-NEAREST NEIGHBOR QUERIES IN ROAD NETWORKS
CN104537858B (en) * 2015-01-15 2016-12-28 盛泽明 Refuel vehicle information promulgating platform in gas station
KR101707742B1 (en) * 2015-07-24 2017-02-17 성균관대학교산학협력단 Optimal location determination method based on maximizing range sum on road network
KR101712847B1 (en) * 2015-11-20 2017-03-07 경북대학교 산학협력단 A method for computing safe exit points of moving k-nearest neighbor queries in directed road networks
US10267645B2 (en) 2016-02-17 2019-04-23 International Business Machines Corporation Method, apparatus and product for efficient solution of nearest object problems
CN108595608B (en) * 2018-04-20 2022-04-29 南京邮电大学 Road network communication scene oriented neighboring object index query method
CN112085236B (en) * 2020-09-04 2023-06-02 武汉大学 Urban hot spot POI detection method and device based on network taxi order data
KR102730409B1 (en) * 2021-12-22 2024-11-15 포항공과대학교 산학협력단 GIS Information Retrieval Method Using Dynamic k-nearest Neighbor Search Algorithm In An Obstacle Environment
KR102687544B1 (en) * 2022-05-23 2024-07-24 엘아이지넥스원 주식회사 Method for generating voronoi diagram for path planning in mission boundary area of unmanned aerial vehicle
CN116164771A (en) * 2023-01-04 2023-05-26 北京踏歌智行科技有限公司 A Real-time Detection Method of Mining Roads Based on Semantic Map

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4862373A (en) * 1987-05-13 1989-08-29 Texas Instruments Incorporated Method for providing a collision free path in a three-dimensional space
JP2001093077A (en) * 1999-09-22 2001-04-06 Fujitsu Ltd Database creation method and device, program recording medium, actual speed information display device, travel time calculation device, and route search device
US20070116357A1 (en) * 2005-11-23 2007-05-24 Agfa-Gevaert Method for point-of-interest attraction in digital images

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
BRPI0508226A (en) * 2004-02-27 2007-07-17 Intergraph Software Tech Co forming a single image from overlay images

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4862373A (en) * 1987-05-13 1989-08-29 Texas Instruments Incorporated Method for providing a collision free path in a three-dimensional space
JP2001093077A (en) * 1999-09-22 2001-04-06 Fujitsu Ltd Database creation method and device, program recording medium, actual speed information display device, travel time calculation device, and route search device
US20070116357A1 (en) * 2005-11-23 2007-05-24 Agfa-Gevaert Method for point-of-interest attraction in digital images

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109253717A (en) * 2018-10-09 2019-01-22 安徽大学 A kind of mining area surface sedimentation 3 D laser scanning surface subsidence monitoring sets station method

Also Published As

Publication number Publication date
WO2009002020A2 (en) 2008-12-31
KR100906313B1 (en) 2009-07-06
KR20080113953A (en) 2008-12-31

Similar Documents

Publication Publication Date Title
WO2009002020A3 (en) Method and system for finding nearest neighbors based on vboronoi diagram
GB2431040B (en) Road map data generation method, road map data update system, and road map data management device
WO2006107488A3 (en) Method and system for transit characteristic prediction
WO2007064637A3 (en) System and method for failover of iscsi target portal groups in a cluster environment
WO2010051510A3 (en) Locating a vehicle
WO2007035653A3 (en) Providing direct access to distributed managed content
WO2008080143A3 (en) Method and system for searching stored data
WO2009032777A3 (en) Method and system for determining an optimally located storage node in a communications network
EP2431277A3 (en) Electrical load management system
WO2013028824A3 (en) Storing and reading multiplexed content
WO2010077972A3 (en) Method and apparatus to implement a hierarchical cache system with pnfs
WO2007062429A3 (en) Systems and methods for classifying and transferring information in a storage network
CA2534222A1 (en) System for optimizing drilling in real time
WO2007131225A3 (en) Identifying a route configured to travel through multiple points of interest
WO2013163644A3 (en) Updating a search index used to facilitate application searches
WO2008042461A3 (en) Systems and methods for storing and searching data in a customer center environment
NO20053075D0 (en) Detail level access control system and method for data stored in relational databases.
WO2008021104A3 (en) Systems and methods for measuring user affinity in a social network environment
WO2005094456A3 (en) Cluster management system and method
WO2008069080A3 (en) Management apparatus and method thereof
WO2010081658A3 (en) Geo-location in a wireless communication network
WO2009088367A3 (en) Profile management method and system
WO2007100928A3 (en) System and method for clustering wireless devices in a wireless network
WO2008024658A8 (en) Intelligent network acquisition for wireless clients
WO2005114374A3 (en) Object-based storage

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 08765895

Country of ref document: EP

Kind code of ref document: A2

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 08765895

Country of ref document: EP

Kind code of ref document: A2