Reference TypeConference Proceedings
Citation KeyAndradeNetoGued:2005:LiAlEx
Author1 Andrade Neto, Pedro Ribeiro de
2 Guedes, André Luiz Pires
Affiliation1 Federal University of Paraná
TitleA linear algorithm for exact pattern matching in planar subdivisions
Conference NameBrazilian Symposium on Computer Graphics and Image Processing, 18 (SIBGRAPI)
EditorRodrigues, Maria Andréia Formico
Frery, Alejandro César
Book TitleProceedings
Date9-12 Oct. 2005
Publisher CityLos Alamitos
PublisherIEEE Computer Society
Conference LocationNatal
Keywordssub-isomorphism, planar subdivisions.
AbstractGraph sub-isomorphism is a very common approach to solving pattern search problems, but this is a NP-complete problem. This way, it is necessary to invest in research of approximate solutions, or in special cases of the problem. Planar subdivisions can be considered as a special case of graphs, because, in addition to nodes and edges, there is a more rigid topology in relation to the order of the edges, arising to the concept of face. This work presents a linear algorithm for pattern search in planar subdivisions. The presented algorithm is based on a hybrid approach between the dual and the region adjacency graph (RAG) to represent the patterns, saving any additional storage cost. Thus, the patterns are looked over the search subdivision, using a region growing algorithm.
Tertiary TypeFull Paper
Size270 KiB
Number of Files1
Target Fileandradep_matchsubdivisions.pdf
Last Update2005: administrator
Metadata Last Update2020: administrator {D 2005}
Document Stagecompleted
Is the master or a copy?is the master
User Grouppedrorib administrator
Content TypeExternal Contribution
source Directory Contentthere are no files
agreement Directory Contentthere are no files
History2005-07-10 17:42:13 :: pedrorib -> banon ::
2005-07-11 12:09:18 :: banon -> pedrorib ::
2008-07-17 14:10:59 :: pedrorib -> banon ::
2008-08-26 15:17:01 :: banon -> administrator ::
2009-08-13 20:37:46 :: administrator -> banon ::
2010-08-28 20:01:18 :: banon -> administrator ::
2020-02-19 03:19:10 :: administrator -> :: 2005
Empty Fieldsaccessionnumber archivingpolicy archivist area callnumber copyholder copyright creatorhistory descriptionlevel dissemination documentstage doi edition electronicmailaddress group holdercode isbn issn label lineage mark mirrorrepository nextedition nexthigherunit notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url versiontype volume
Access Date2020, Nov. 28