DC Field | Value | Language |
---|---|---|
dc.contributor.author | CHOI, SH | ko |
dc.contributor.author | Shin, Sung-Yong | ko |
dc.contributor.author | Chwa, Kyung Yong | ko |
dc.date.accessioned | 2013-02-27T15:27:49Z | - |
dc.date.available | 2013-02-27T15:27:49Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 1995-07 | - |
dc.identifier.citation | ALGORITHMICA, v.14, no.1, pp.27 - 51 | - |
dc.identifier.issn | 0178-4617 | - |
dc.identifier.uri | http://hdl.handle.net/10203/69345 | - |
dc.description.abstract | A funnel, which is notable for its fundamental role in visibility algorithms, is defined as a polygon that has exactly three convex vertices, two of which are connected by a boundary edge. In this paper we investigate the visibility graph of a funnel which we call an F-graph. We first present two characterizations of an F-graph, one of whose sufficiency proof itself is a linear time Real RAM algorithm for drawing a funnel on the plane that corresponds to an F-graph. We next give a linear-time algorithm for recognizing an F-graph. When the algorithm recognizes an F-graph, it also reports one of the Hamiltonian cycles defining the boundary of its corresponding funnel. This recognition algorithm takes linear time even on a RAM. We finally show that an F-graph is weakly triangulated and therefore perfect, which agrees with the fact that perfect graphs are related to geometric structures. | - |
dc.language | English | - |
dc.publisher | SPRINGER VERLAG | - |
dc.subject | TRIANGULATED SIMPLE POLYGONS | - |
dc.subject | ALGORITHM | - |
dc.title | CHARACTERIZING AND RECOGNIZING THE VISIBILITY GRAPH OF A FUNNEL-SHAPED POLYGON | - |
dc.type | Article | - |
dc.identifier.wosid | A1995QZ93900002 | - |
dc.identifier.scopusid | 2-s2.0-34248641532 | - |
dc.type.rims | ART | - |
dc.citation.volume | 14 | - |
dc.citation.issue | 1 | - |
dc.citation.beginningpage | 27 | - |
dc.citation.endingpage | 51 | - |
dc.citation.publicationname | ALGORITHMICA | - |
dc.contributor.localauthor | Shin, Sung-Yong | - |
dc.contributor.localauthor | Chwa, Kyung Yong | - |
dc.contributor.nonIdAuthor | CHOI, SH | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | COMPUTATIONAL GEOMETRY | - |
dc.subject.keywordAuthor | FUNNEL-SHAPED POLYGON | - |
dc.subject.keywordAuthor | VISIBILITY GRAPH | - |
dc.subject.keywordAuthor | CHARACTERIZING AND RECOGNIZING VISIBILITY GRAPHS | - |
dc.subject.keywordAuthor | WEAKLY TRIANGULATED GRAPH | - |
dc.subject.keywordAuthor | PERFECT GRAPH | - |
dc.subject.keywordPlus | TRIANGULATED SIMPLE POLYGONS | - |
dc.subject.keywordPlus | ALGORITHM | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.