{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T17:22:32Z","timestamp":1775323352234,"version":"3.50.1"},"reference-count":31,"publisher":"ASME International","issue":"4","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2001,12,1]]},"abstract":"<jats:p>Non-manifold boundary representations have become very popular in recent years and various representation schemes have been proposed, as they represent a wider range of objects, for various applications, than conventional manifold representations. As these schemes mainly focus on describing sufficient adjacency relationships of topological entities, the models represented in these schemes occupy storage space redundantly, although they are very efficient in answering queries on topological adjacency relationships. To solve this problem, in this paper, we propose a compact as well as fast non-manifold boundary representation, called the partial entity structure. This representation reduces the storage size to half that of the radial edge structure, which is one of the most popular and efficient of existing data structures, while allowing full topological adjacency relationships to be derived without loss of efficiency. In order to verify the time and storage efficiency of the partial entity structure, the time complexity of basic query procedures and the storage requirement for typical geometric models are derived and compared with those of existing schemes.<\/jats:p>","DOI":"10.1115\/1.1433486","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T09:03:10Z","timestamp":1027760590000},"page":"356-365","update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":27,"title":["Partial Entity Structure: A Compact Boundary Representation for Non-Manifold Geometric Modeling"],"prefix":"10.1115","volume":"1","author":[{"given":"Sang Hun","family":"Lee","sequence":"first","affiliation":[{"name":"Graduate School of Automotive Engineering, Kookmin University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunwoo","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Mechanical and Aerospace Engineering, Seoul National University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2001,11,1]]},"reference":[{"key":"2019100521570869100_r1","doi-asserted-by":"crossref","unstructured":"Charlesworth, W. W., and Anderson, D. C., 1995, \u201cApplications of Non-manifold Topology,\u201d Proceedings of International Computers in Engineering Conference and the ASME Engineering Database Symposium, Boston, MA, pp. 103\u2013112.","DOI":"10.1115\/CIE1995-0737"},{"key":"2019100521570869100_r2","doi-asserted-by":"crossref","unstructured":"Sriram, R. D., Wong, A., and He, L.-X., 1995, \u201cGNOMES: An Object-oriented Nonmanifold Geometric Engine,\u201d Comput.-Aided Des., 27, No. 11, pp. 853\u2013868.","DOI":"10.1016\/0010-4485(95)00022-4"},{"key":"2019100521570869100_r3","doi-asserted-by":"crossref","unstructured":"Saxena, M., Finnigan, P. M., Graichen, C. M., Hathaway, A. F., and Parthasarathy, V. N., 1995, \u201cOctree-Based Automatic Mesh Generation for Non-Manifold Domains,\u201d Eng. Comput., 11, pp. 1\u201314.","DOI":"10.1007\/BF01230440"},{"key":"2019100521570869100_r4","doi-asserted-by":"crossref","unstructured":"Shimada, K., and Gossard, D. C., 1995, \u201cBubble Mesh: Automated Triangular Meshing of Non-manifold Geometry by Sphere Packing,\u201d Proceedings of the 3rd Symposium on Solid Modeling and Applications, Salt Lake City, UT, pp. 409\u2013419.","DOI":"10.1145\/218013.218095"},{"key":"2019100521570869100_r5","unstructured":"Gursoz, E. L., Choi, Y., and Prinz, F. B., 1990, \u201cVertex-based Boundary Representation of Non-manifold Boundaries,\u201d Wozny, M. J., Turner, J. U., and Preiss, K., editors, Geometric Modeling for Product Engineering, North-Holland, pp. 107\u2013130."},{"key":"2019100521570869100_r6","doi-asserted-by":"crossref","unstructured":"Gursoz, E. L., Choi, Y., and Prinz, F. B., 1991, \u201cBoolean Set Operations on Non-Manifold Boundary Representation Objects,\u201d Comput.-Aided Des., 23, No. 1, pp. 33\u201339.","DOI":"10.1016\/0010-4485(91)90079-C"},{"key":"2019100521570869100_r7","unstructured":"Weiler, K., 1988, \u201cThe Radial Edge Structure: a Topological Representation for Non-manifold Geometric Boundary Modeling,\u201d M. J. Wozny, H. W. McLauhlin, and J. L. Encarnc\u00b8ao, editors, Geometric Modeling for CAD Applications, North-Holland, pp. 3\u201336."},{"key":"2019100521570869100_r8","doi-asserted-by":"crossref","unstructured":"Crocker, G. A., and Reinke, W. F., 1991, \u201cAn Editable Non-manifold Boundary Representation,\u201d IEEE Comput. Graphics Appl., 11, No. 2, pp. 39\u201351, March.","DOI":"10.1109\/38.75589"},{"key":"2019100521570869100_r9","doi-asserted-by":"crossref","unstructured":"Masuda, H. , 1992, \u201cTopological Operators and Boolean Operations for Complex-based Nonmanifold Geometric Models,\u201d Comput.-Aided Des., 25, No. 2, pp. 119\u2013129.","DOI":"10.1016\/0010-4485(93)90097-8"},{"key":"2019100521570869100_r10","unstructured":"Pratt, M. J., 1990, \u201cA Hybrid Feature-based Modeling System,\u201d F. L. Krause and H. Jansen, editors, North-Holland, pp. 189\u2013201."},{"key":"2019100521570869100_r11","unstructured":"Weiler, K., 1990, \u201cGeneralized Sweep Operations in the Non-manifold Environment,\u201d Geometric Modeling for Product Engineering, M. J. Wozny, J. U. Turner, and K. Preiss, editors, Elsevier Science North-Holland."},{"key":"2019100521570869100_r12","doi-asserted-by":"crossref","unstructured":"Lee, S. H., 1999, \u201cOffsetting Operations in Non-manifold Geometric Modeling,\u201d Proceedings of the 5th ACM Symposium on Solid Modeling and Applications, Ann Arbor, Michigan, pp. 42\u201353.","DOI":"10.1145\/304012.304017"},{"key":"2019100521570869100_r13","doi-asserted-by":"crossref","unstructured":"Yamaguchi, Y., and Kimura, F., 1995, \u201cNonmanifold Topology Based on Coupling Entities,\u201d IEEE Comput. Graphics Appl., 15, No. 1, pp. 42\u201350.","DOI":"10.1109\/38.364963"},{"key":"2019100521570869100_r14","unstructured":"Choi, Y., 1989, \u201cVertex-based Boundary Representation of Non-manifold Geometric Models,\u201d PhD. Thesis, Carnegie Mellon University."},{"key":"2019100521570869100_r15","unstructured":"Rossignac, J., and O\u2019Conner, M. A., 1990, \u201cSGC: A Dimensional-independent Model for Pointsets with Internal Structures and Incomplete Boundaries,\u201d Geometric Modeling for Product Engineering, North-Holland, pp. 145\u2013180."},{"key":"2019100521570869100_r16","doi-asserted-by":"crossref","unstructured":"Lienhardt, P. , 1991, \u201cTopological Models for Boundary Representation: A Comparison with n-dimensional Generalized Maps,\u201d Comput.-Aided Des., 23, No. 1, pp. 59\u201382.","DOI":"10.1016\/0010-4485(91)90082-8"},{"key":"2019100521570869100_r17","unstructured":"Lee, S. H., and Lee, K., 1996, \u201cCompact Boundary Representation and Generalized Euler Operators for Non-manifold Geometric Modeling,\u201d Transaction of the SCCE, 1, No. 1, pp. 1\u201319 (in Korean)."},{"key":"2019100521570869100_r18","doi-asserted-by":"crossref","unstructured":"Lee, S. H. and Lee, K., 2001, \u201cPartial Entity Structure: A Fast and Compact Non-Manifold Boundary Representation Based on Partial Topological Entities,\u201d The Sixth ACM Symposium on Solid Modeling and Applications, Ann Arbor, pp. 159\u2013170.","DOI":"10.1145\/376957.376976"},{"key":"2019100521570869100_r19","doi-asserted-by":"crossref","unstructured":"Brisson, E., 1989, \u201cRepresenting Geometric Structures in d Dimensions: Topology and Order,\u201d Proceedings of the 5th ACM Symposium on Computational Geometry, ACM Press, New York, pp. 218\u2013227.","DOI":"10.1145\/73833.73858"},{"key":"2019100521570869100_r20","doi-asserted-by":"crossref","unstructured":"Lienhardt, P., \u201cSubdivision of N-Dimensional Spaces and N-Dimensional Generalized Maps,\u201d Proceedings of the 5th ACM Symposium on Computational Geometry, ACM Press, New York, pp. 228\u2013236, 1989","DOI":"10.1145\/73833.73859"},{"key":"2019100521570869100_r21","doi-asserted-by":"crossref","unstructured":"Hansen, H. O\u0338. and Christensen N. J., 1993, \u201cA Model for n- Dimensional Boundary Topology,\u201d Proceedings of the 2nd ACM Symposium on Solid Modeling and Applications, Montreal, Canada, pp. 65\u201373.","DOI":"10.1145\/164360.164386"},{"key":"2019100521570869100_r22","doi-asserted-by":"crossref","unstructured":"Guibas, L., and Stolfi, J., 1985, \u201cPrimitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams,\u201d ACM Trans. Graphics, 4, No. 2, pp. 74\u2013123.","DOI":"10.1145\/282918.282923"},{"key":"2019100521570869100_r23","doi-asserted-by":"crossref","unstructured":"Dobkin, D. P. and Laszlo, M. M., 1987, \u201cPrimitives for the Manipulation of Three-Dimensional Subdivisions,\u201d Proceedings of the 3rd ACM Symposium on Computational Geometry, ACM Press, New York, pp. 86\u201399.","DOI":"10.1145\/41958.41967"},{"key":"2019100521570869100_r24","doi-asserted-by":"crossref","unstructured":"Woo, T. C. , 1985, \u201cA Combinational Analysis of Boundary Data Structure Schemata,\u201d IEEE Comput. Graphics Appl., 5, No. 3, pp. 19\u201327.","DOI":"10.1109\/MCG.1985.276337"},{"key":"2019100521570869100_r25","doi-asserted-by":"crossref","unstructured":"Baumgart, B., 1972, \u201cWinged-edge Polyhedron Representation,\u201d Technical Report CS-320 Stanford Artificial Intelligence Laboratory, Stanford University, CA.","DOI":"10.21236\/AD0755141"},{"key":"2019100521570869100_r26","unstructured":"Solid Modeling Solutions, http:\/\/www.smlib.com"},{"key":"2019100521570869100_r27","doi-asserted-by":"crossref","unstructured":"Cavalcanti, P. R., Carvalho, P. C. P., and Martha, L. F., 1997, \u201cNon-manifold Modeling: An Approach Based on Spatial Subdivision,\u201d Comput.-Aided Des., 29, No. 3, pp. 209\u2013220.","DOI":"10.1016\/S0010-4485(96)00066-8"},{"key":"2019100521570869100_r28","unstructured":"Marcheix, D., and Gueorguieva, S., 1997, \u201cTopological Operators for Non- manifold Modeling,\u201d Proceedings of the 30th International Symposium on Automotive Technology and Automation, Mechatronics\/Automotive Electronics, Florence, Italy, pp. 173\u2013186."},{"key":"2019100521570869100_r29","unstructured":"Mantyla, M., 1988, \u201cAn Introduction to Solid Modeling,\u201d Computer Science Press."},{"key":"2019100521570869100_r30","unstructured":"Spatial Technology Inc., 1999, ACIS 3D Toolkit 5.0,"},{"key":"2019100521570869100_r31","unstructured":"Wilson, P. R., 1988, \u201cData Transfer and Solid Modeling,\u201d Geometric Modeling for CAD Applications, M. M. Wony, H. W. McLaughlin, and J. L. Encarnacao editors, Elsevier Science Publishers B. V., North-Holland, pp. 217\u2013254."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/1\/4\/356\/5668214\/356_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/1\/4\/356\/5668214\/356_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,8]],"date-time":"2024-12-08T16:37:10Z","timestamp":1733675830000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/1\/4\/356\/471622\/Partial-Entity-Structure-A-Compact-Boundary"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,11,1]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2001,12,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.1433486","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"value":"1530-9827","type":"print"},{"value":"1944-7078","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,11,1]]}}}