AN OPTIMAL ALGORITHM FOR EXTRACTING THE REGIONS OF A PLANE GRAPH

Authors
JIANG XY BUNKE H
Citation
Xy. Jiang et H. Bunke, AN OPTIMAL ALGORITHM FOR EXTRACTING THE REGIONS OF A PLANE GRAPH, Pattern recognition letters, 14(7), 1993, pp. 553-558
Citations number
5
Categorie Soggetti
Computer Sciences, Special Topics","Computer Applications & Cybernetics
Journal title
Pattern recognition letters → ACNP
ISSN journal
01678655
Volume
14
Issue
7
Year of publication
1993
Pages
553 - 558
Database
ISI
SICI code
0167-8655(1993)14:7<553:AOAFET>2.0.ZU;2-Y
Abstract
In a recent paper, Fan and Chang (1991) presented an algorithm for ext racting all regions of a plane graph. It is shown in this paper that t heir algorithm has quadratic time and space complexity. We propose an optimal algorithm which takes O(m log m) computation time and uses O(m ) space, where m is the number of edges of the plane graph. The optima lity of our algorithm is established by proving an OMEGA(m log m) lowe r bound under the algebraic decision-tree model.