Show simple item record

dc.contributor.authorLien, Jyh-Mingen_US
dc.contributor.editorM. Botsch and R. Pajarola and B. Chen and M. Zwickeren_US
dc.date.accessioned2014-01-29T16:52:10Z
dc.date.available2014-01-29T16:52:10Z
dc.date.issued2007en_US
dc.identifier.isbn978-3-905673-51-7en_US
dc.identifier.issn1811-7813en_US
dc.identifier.urihttp://dx.doi.org/10.2312/SPBG/SPBG07/073-080en_US
dc.description.abstractSimplification or decomposition is a common strategy to handle large geometric models, which otherwise require excessive computation to process. Star-shaped decomposition partitions a model into a set of star-shaped components. A model is star shaped if and only if there exists at least one point which can see all the points of the model. Due to this interesting property, decomposing a model into star-shaped components can be used for computing camera locations to guard a given environment (the art-gallery problem), skeleton extraction, point data compression, as well as motion planning. In this paper, we propose a simple method to partition (or cluster) point set data (PSD) into 'approximately star-shaped' components. Our method can be applied to both 2D and 3D PSD and can be naturally extended to higher dimensional spaces. Our method does not require or compute any connectivity information of the input points. The proposed method only requires the position and the outward normals of points. Our experimental results show that the size of the final decomposition is close to optimal.en_US
dc.publisherThe Eurographics Associationen_US
dc.subjectCategories and Subject Descriptors (according to ACM CCS): I.3.5 [Computing Methodologies]: Computer Graphics[ Computational Geometry and Object Modeling]en_US
dc.titleApproximate Star-Shaped Decomposition of Point Set Dataen_US
dc.description.seriesinformationEurographics Symposium on Point-Based Graphicsen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record