Crystal voronoi diagram and its applications to collision-free paths

Kei Kobayashi, Kokichi Sugihara

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)


This paper studies the multiplicatively weighted crystal- growth Voronoi diagram, which describes the partition of the plane into crystals with different growth speeds. This type of the Voronoi diagram is defined, and its basic properties are investigated. An approximation algorithm is proposed. This algorithm is based on a finite difference method, called a fast marching method, for solving a special type of a partial differential equation. The proposed algorithm is applied to the planning of a collision-free path for a robot avoiding enemy attacks.

Original languageEnglish
Title of host publicationComputational Science - ICCS 2001 - International Conference, 2001, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540422323, 9783540422327
Publication statusPublished - 2001
Externally publishedYes
EventInternational Conference on Computational Science, ICCS 2001 - San Francisco, United States
Duration: 2001 May 282001 May 30

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


OtherInternational Conference on Computational Science, ICCS 2001
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science


Dive into the research topics of 'Crystal voronoi diagram and its applications to collision-free paths'. Together they form a unique fingerprint.

Cite this