微信服务号

微信订阅号

2025-4-25- 14
Home > Archive>Volume 19, Issue 4, 2008 >1026-1035
PDF HTML XML Export Cite reminder
NP-Hardness of Some Polyhedral Mesh Decomposition Problems
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [25]
    • |
  • Related [20]
    • |
  • Cited by [1]
    • | |
  • Comments
    Abstract:

    This paper considers the problem of decomposing a polyhedral surface or a polyhedron into simpler components: Monotone patches or terrain polyhedra. It is shown to be NP-complete to decide if a polyhedral surface can be decomposed into k monotone patches, by constructing a geometric model to make a reduction from SAT (satisfiability) problem. And the corresponding optimization problem is shown to be NP-hard. Then, the method is extended to the problems of decomposing a polyhedron with or without holes into the minimum number of terrain polyhedra, both of which are also shown to be NP-hard.

    Reference
    [1]Biederman I.Recognition-by-Components:A theory of human image understanding.Psychological Review,1987,94(2):115-147.
    [2]Biederman I.Visual cognition and action.An Invitation to Cognitive Science,1990,2(2):41-72.
    [3]Hoffman DD,Richards W.Parts of recognition.Cognition,1984,18(1):65-96.
    [4]Hoffman DD,Singh M.Salience of visual parts.Cognition,1997,63(1):29-78.
    [5]Gregory AD,State A,Lin MC,Manocha D,Livingston MA.Feature-Based surface decomposition for correspondence and morphing between polyhedra.In:Proc.of the 15th Annual Symp.on Computational Geometry (SCG'99).ACM Press,1999.415-416.http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel4/5596/14988/00681909.pdf?temp=x
    [6]Shlafman S,Tal A,Katz S.Metamorphosis of polyhedral surfaces using decomposition.Computer Graphics Forum (Proc.of the Eurographics),2002,21(3):219-228.
    [7]Alexa M.Recent advances in mesh morphing.Computer Graphics Forum,2002,21(2):173-196.
    [8]Zhao Y,Ong HY,Tan TS,Xiao Y.Interactive control of component-based morphing.In:Proc.of the 2003 ACM SIGGRAPH/ Eurographics Symp.on Computer animation (SCA 2003).Eurographics Association,2003.339-348.http://portal.acm.org/ citation.cfm?id=846324
    [9]Ehmann SA,Lin MC.Accurate and fast proximity queries between polyhedra using convex surface decomposition.Computer Graphics Forum (Proc.of the Eurographics),2001,20(3):500-510.
    [10]Li X,Deng J,Paul JC.Realtime collision detection based on monotone clusters.In:Proc.of the Pacific Graphics.Macau,2005.61-63.
    [11]Li X,Woon TW.Decomposing polygon meshes for interactive applications.In:Proc.of the 2001 Symp.on Interactive 3D Graphics (SI3D 2001).ACM Press,2001.35-42.http://portal.acm.org/citation.cfm?id=364338.364343
    [12]Katz S,Tal A.Hierarchical mesh decomposition using fuzzy clustering and cuts.ACM Trans.on Graphics,2003,22(3):954-961.
    [13]Maillot J,Yahia H,Verroust A.Interactive texture mapping.In:Proc.of the 20th Annual Conf.on Computer Graphics and Interactive Techniques (SIGGRAPH'93).ACM Press,1993.27-34.http://portal.acm.org/citation.cfm?id=166120
    [14]Leeb V,Radetzky A,Auer LM.Interactive texturing by polyhedron decomposition.In:IEEE Proc.of the Virtual Reality.2001.165-171.http://portal.acm.org/citation.cfm?id=580521.835856
    [15]Sander PV,Snyder J,Gortler SJ,Hoppe H.Texture mapping progressive meshes.In:Computer Graphics Proc.of the Annual Conf.Series,ACM SIGGRAPH.Los Angeles,2001.409-416.http://portal.acm.org/citation.cfm?id=383307
    [16]Lévy B,Petitjean S,Ray N,Maillot J.Least squares conformal maps for automatic texture atlas generation.In:Proc.of the 29th Annual Conf.on Computer Graphics and Interactive Techniques (SIGGRAPH 2002).San Antonio:ACM Press,2002.http://portal.acm.org/citation.cfm?id=566654.566590
    [17]Garland M,Willmott A,Heckbert PS.Hierarchical face clustering on polygonal surface.In:Proc.of the ACM Symp.on Interactive 3D Graphics,Research Triangle Park.North Carolina,2001.49-58.http://portal.acm.org/citation.cfm?id=364345
    [18]Zuckerberger E,Tal A,Shlafman S.Polyhedral surface decomposition with applications.Computers and Graphics,2002,26(5):733-743.
    [19]Lingas A.The power of non-rectilinear holes.Languages and Programming (Proc.of the 9th Colloquium on Automata),1982,140:369-383.
    [20]Chazelle B.Convex partitions of polyhedra:A lower bound and worst-case optimal algorithm.SIAM Journal on Computing,1984,13(3):488-507.
    [21]Chazelle B,Palios L.Decomposing the boundary of a non-convex polyhedron.Algorithmica,1997,17(3):245-265.
    [22]Chazelle B,Dobkin DP,Shouraboura N,Tal A.Strategies for polyhedral surface decomposition:An experimental study.Computational Geometry:Theory and Applications,1997,7:327-342.
    [23]Cormen TH,Leiserson CE,Rivest RL,Stein C.Introduction to Algorithms.2nd ed.,The MIT Press,2001.
    [24]Zhang C,Chen T.Efficient feature extraction for 2D/3D objects in mesh representation.In:Proc.of the IEEE Int'l Conf.on Image Processing.Thessaloniki,2001.935-938.http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=958278
    [25]Fekete SP,Mitchell JSB.Terrain decomposition and layered manufacturing.Int'l Journal of Computational Geometry & Applications,2001,11(6):647-668.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

田延军,邓俊辉.几个多面体网格剖分问题的NP难度证明.软件学报,2008,19(4):1026-1035

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 04,2006
  • Revised:November 14,2006
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038704Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063