DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bae, Sang-Won | ko |
dc.contributor.author | Lee, Chun-Seok | ko |
dc.contributor.author | Ahn, Hee-Kap | ko |
dc.contributor.author | Choi, Sung-Hee | ko |
dc.contributor.author | Chwa, Kyung-Yong | ko |
dc.date.accessioned | 2011-02-14T01:35:22Z | - |
dc.date.available | 2011-02-14T01:35:22Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.42, no.9, pp.903 - 912 | - |
dc.identifier.issn | 0925-7721 | - |
dc.identifier.uri | http://hdl.handle.net/10203/22088 | - |
dc.description.abstract | We study the problems of computing two non-convex enclosing shapes with the minimum area: the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n(2)) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space. (C) 2009 Elsevier B.V. All rights reserved. | - |
dc.description.sponsorship | This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD, Basic Research Promotion Fund) (KRF-2007-331-D00372) and by the Brain Korea 21 Project. | en |
dc.language | English | - |
dc.language.iso | en_US | en |
dc.publisher | Elsevier Science Bv | - |
dc.title | Computing minimum-area rectilinear convex hull and L-shape | - |
dc.type | Article | - |
dc.identifier.wosid | 000268622400008 | - |
dc.identifier.scopusid | 2-s2.0-84867975189 | - |
dc.type.rims | ART | - |
dc.citation.volume | 42 | - |
dc.citation.issue | 9 | - |
dc.citation.beginningpage | 903 | - |
dc.citation.endingpage | 912 | - |
dc.citation.publicationname | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | - |
dc.identifier.doi | 10.1016/j.comgeo.2009.02.006 | - |
dc.embargo.liftdate | 9999-12-31 | - |
dc.embargo.terms | 9999-12-31 | - |
dc.contributor.localauthor | Choi, Sung-Hee | - |
dc.contributor.localauthor | Chwa, Kyung-Yong | - |
dc.contributor.nonIdAuthor | Lee, Chun-Seok | - |
dc.contributor.nonIdAuthor | Ahn, Hee-Kap | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Rectilinear convex hull | - |
dc.subject.keywordAuthor | L-shape | - |
dc.subject.keywordAuthor | Enclosing shapes | - |
dc.subject.keywordAuthor | Extremal points | - |
dc.subject.keywordAuthor | Staircases | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.