IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Recent publications  
    Author's Guide  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 31, Number 3, Page 361 (1987)
Computer-aided Design
  Full article: arrowPDF   arrowCopyright info


Voronoi diagram for multiply-connected polygonal domains I: Algorithm

by V. Srinivasan, L. R. Nackman
Voronoi diagrams of multiply-connected polygonal domains (polygons with holes) can be of use in computer-aided design. We describe a simple algorithm that computes such Voronoi diagrams in O(N(log2 N+H)) time, where N is the number of edges and H is the number of holes.
Related Subjects: Algorithms; Computer-aided design; Graphics; Mathematics (applied)