Splitting a complex of convex polytopes in any dimension

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Splitting a complex of convex polytopes in any dimension

Full text

Pdf (1.06 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twelfth annual symposium on Computational geometry table of contents

Philadelphia, Pennsylvania, United States

Pages: 88 - 97

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Chandrajit L. Bajaj	Computer Sciences Department, Purdue University, West Lafayette, IN
Valerio Pascucci	Computer Sciences Department, Purdue University, West Lafayette, IN

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 20, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237218.237246 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AGARWAL, R K., AND MATOU~EK, J. On range searching with semialgebraic sets. Discrete Comput. Geom. 1 / (1994), 393-418.
	2	AGARWAL, R K., AND MAT()U,~EK, j. Dynamic halfspace range reporting ,and its applications. Algorithmica 13 (1995), 325-345.
	3	Chanderjit L. Bajaj , Tamal K. Dey, Convex decomposition of polyhedra and robustness, SIAM Journal on Computing, v.21 n.2, p.339-364, April 1992 [doi>10.1137/0221025]
	4	BERN, M., AND EPPSTEIN, D. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry, D.-Z. Du ,and F. K. Hwang, Eds., vol. i of Lecture Notes Series on Computing. World Scientific, Singapore, 1992, pp. 23-90.
	5	BRISSON, E. Representing geometric structures in d dimensions: Topology ,and order. Discrete Comput. Geom. 9 (1993), 387-426.
	6	Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
	7	B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
	8	DOBKIN, D. R, AND KIRKPATRICK, D. G. Fast detection of polyhedral intersection. Theoret. Comput. Sci. 27 (1983), 241-253.
	9	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	10	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	11	Steven Fortune , Victor Milenkovic, Numerical stability of algorithms for line arrangements, Proceedings of the seventh annual symposium on Computational geometry, p.334-341, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109685]
	12	GR/)NBAUM, B. Convex Polytopes. Wiley, New York, NY, 1967.
	13	HOPC~ROFT, J. E., AND KAHN, P.J. A p,'u'adigln for robust geometric ,algorithms. Algorithmica 7 (1992), 339-380.
	14	KINCSES, J. On polytopescut by flats. Discrete Comput. Geom. 14 (1995), 287-294.
	15	Zhenyu Li , Victor Milenkovic, Constructing strongly convex hulls using exact or rounded arithmetic, Proceedings of the sixth annual symposium on Computational geometry, p.235-243, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98577]
	16	LIENHARDT, P. N-dimensional gener~dized combinatorial maps ,and cellular quasi-manifolds, international Journal of Computational Geometry & Applications 4, 3 (1994), 275-324.
	17	William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
	18	MATOU~EK, J. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10, 2 (1993), 157-182.
	19	Nelson Max , Pat Hanrahan , Roger Crawfis, Area and volume coherence for efficient visualization of 3D scalar functions, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.27-33, Nov. 1990
	20	MILENKOVIC, V. Robust polygon modeling. Computer- Aided Design 25, 9 (1993). (special issue on Uncertainties in Geometric Design).
	21	MULMULEY, K. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
	22	NAYLOR, B. Constructing good partitioning trees. In Proc. Graphics Interface '93 (Toronto, ON, 1993), pp. 181-191.
	23	Bruce Naylor , John Amanatides , William Thibault, Merging BSP trees yields polyhedral set operations, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.115-124, Aug. 1990
	24	A. Paoluzzi , F. Bernardini , C. Cattani , V. Ferrucci, Dimension-independent modeling with simplicial complexes, ACM Transactions on Graphics (TOG), v.12 n.1, p.56-102, Jan. 1993 [doi>10.1145/169728.169719]
	25	Valerio Pascucci , Vincenzo Ferrucci , Alberto Paoluzzi, Dimension-independent convex-cell based HPC: representation scheme and implementation issues, Proceedings of the third ACM symposium on Solid modeling and applications, p.163-174, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218055]
	26	Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
	27	STEWART, A. J. Local robustness ,and its application to polyhedral intersection. International Journal of Computational Geometry & Applications 4, 1 (1994), 87- 118.
	28	SUGIHARA, K. A robust ,and consistent algorithm for intersecting convex polyhedra. Comput. Graph. Forum 13, 3 (1994), 45-54. Proc. EUROGRAPHICS '94.
	29	William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.153-162, August 1987
	30	TROTTER, W. T Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins Series in the Mathematical Sciences. The Johns Hopkins University Press, 1992.
	31	VANi~:EK JR., G. Brep-index: a multidimensional space partitioning tree. !nternat. J. Comput. Geom. Appl. 1, 3 ( 1991), 243-261.

CITED BY 5

	Chandrajit L. Bajaj , Valerio Pascucci , Ariel Shamir , Robert J. Holt , Arun N. Netravali, Dynamic maintenance and visualization of molecular surfaces, Discrete Applied Mathematics, v.127 n.1, p.23-51, April 2003
	S. Nirenstein , E. Blake , J. Gain, Exact from-region visibility culling, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
	A. Paoluzzi , V. Pascucci , G. Scorzelli, Progressive dimension-independent Boolean operations, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Antonio DiCarlo , Franco Milicchio , Alberto Paoluzzi , Vadim Shapiro, Solid and physical modeling with chain complexes, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
	F. Milicchio , A. DiCarlo , A. Paoluzzi , V. Shapiro, A codimension-zero approach to discretizing and solving field problems, Advanced Engineering Informatics, v.22 n.2, p.172-185, April, 2008