Reduction of the search space in the edge-tracing algorithm for the Voronoi diagram of 3D balls

Youngsong Cho, Donguk Kim, Hyun Chan Lee, Joon Young Park, Deok Soo Kim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations

Abstract

Voronoi diagram for 3D balls can be applicable to various fields in science and engineering. The edge-tracing algorithm constructs the Voronoi diagram in 0(mn) time in the worst-case where m and n are the numbers of edges and balls, respectively. The computation time of the algorithm is dominated by finding the end vertex of a given edge since all edges in the Voronoi diagram should be traced essentially. In this paper, we define the feasible region which a ball to define the end vertex of a given edge should intersect. Then, balls which do not intersect the feasible region are filtered out before finding an end vertex since they cannot define an end vertex. Therefore, we improve the runtime-performance of the edge-tracing algorithm via the feasible region.

Original languageEnglish
Title of host publicationComputational Science and Its Applications - ICCSA 2006
Subtitle of host publicationInternational Conference, Proceedings - Part I
PublisherSpringer Verlag
Pages111-120
Number of pages10
ISBN (Print)354034070X, 9783540340706
DOIs
StatePublished - 2006
EventICCSA 2006: International Conference on Computational Science and Its Applications - Glasgow, United Kingdom
Duration: 8 May 200611 May 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3980 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceICCSA 2006: International Conference on Computational Science and Its Applications
Country/TerritoryUnited Kingdom
CityGlasgow
Period8/05/0611/05/06

Keywords

  • Edge-tracing algorithm
  • Feasible region
  • Voronoi diagram for balls

Fingerprint

Dive into the research topics of 'Reduction of the search space in the edge-tracing algorithm for the Voronoi diagram of 3D balls'. Together they form a unique fingerprint.

Cite this