Erased Arrangements of Lines and Convex Decompositions of Polyhedra

Erased Arrangements of Lines and Convex Decompositions of Polyhedra (1997) (Make Corrections) (1 citation)
J. E. Hershberger, J. S. SnoeyinkComputational Geometry. Theory and Applications

Home/Search Context Related

View or download:
cs.ubc.ca/spider/snoeyin...erased.ps.gz
unc.edu/~snoeyink/papers...erased.ps.gz
Cached:  PS.gz  PS  PDF  DjVu  Image  Update  Help

From:  cs.ubc.ca/spider/snoeyin...papers (more)
Homepages:  J.Hershberger  J.Snoeyink
  HPSearch  (Update Links)

Rate this article:

(best)
Comment on this article

(Enter summary)
Abstract: In 1984, B. Chazelle [SIAM J. Comp., 13 (1984), pp. 488--507] proposed a notch-cutting procedure for decomposing a non-convex polyhedron into convex pieces. This paper shows that notch-cutting, when applied to a polyhedron with n faces and r reflex dihedral angles, gives a convex decomposition with \Theta(nr + r 7=3 ) worst-case complexity. The upper and lower bounds are obtained by studying the complexity of the horizon of a segment in an incrementally-constructed erased arrangement of n... (Update)

Context of citations to this paper: More

...if their interiors do not intersect. They correspond to (a subset of) cells in what Hershberger and Snoeyink call erased arrangements [HS98] and Dey and Shah call convex arrangements [DS94] As already noted, K dis (k; n; d) K c (k; n; d) In fact, K dis (k; n; 2) k...

Cited by: More
Polytopes in Arrangements - Boris Aronov Tamal (1999) (Correct)

Active bibliography (related documents): More All
0.4: Davenport-Schinzel Sequences and Their Geometric Applications - Agarwal, Sharir (1995) (Correct)
0.3: Cartographic Line Simplification and Polygon CSG Formulae.. - Hershberger, Snoeyink (1998) (Correct)
0.3: An Efficient Algorithm for Finding the CSG.. - Dobkin, Guibas.. (1989) (Correct)

Similar documents based on text: More All
0.4: On the Time Bound for Convex Decomposition of Simple Polygons - Keil (1998) (Correct)
0.4: Determining Mode I And Mode Ii Contributions In End Notched .. - John Hermanson Lawrence (1998) (Correct)
0.3: Efficiently Planning Compliant Motion In The Plane - Friedman, Hershberger, Snoeyink (1996) (Correct)

BibTeX entry: (Update)

J. E. Hershberger and J. S. Snoeyink. Erased arrangements of lines and convex decompositions of polyhedra. Comput. Geom. Theory Appl., 9:129-143, 1998. http://citeseer.nj.nec.com/hershberger97erased.html More

@article{ hershberger98erased,
    author = "J. E. Hershberger and J. S. Snoeyink",
    title = "Erased arrangements of lines and convex decompositions of polyhedra",
    journal = "Computational Geometry. Theory and Applications",
    volume = "9",
    number = "3",
    pages = "129--143",
    year = "1998",
    url = "citeseer.nj.nec.com/hershberger97erased.html" }

Citations (may not include all citations):
417 Algorithms in Combinatorial Geometry (context) - Edelsbrunner - 1987
268 Applications of random sampling in computational geometry - Clarkson, Shor - 1989
219 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
89 Combinatorial complexity bounds for arrangements of curves a.. (context) - Clarkson, Edelsbrunner et al. - 1990
68 Constructing arrangements of lines and hyperplanes with appl.. (context) - Edelsbrunner, O'Rourke et al. - 1986
65 Nonlinearity of Davenport-Schinzel sequences and of generali.. (context) - Hart, Sharir - 1986
55 The power of geometric duality (context) - Chazelle, Guibas et al. - 1985
53 Efficient binary space partitions for hidden-surface removal.. (context) - Paterson, Yao - 1990
34 Convex partitions of polyhedra: A lower bound and worst-case.. (context) - Chazelle - 1984
23 the difficulty of triangulating three-dimensional nonconvex .. (context) - Ruppert, Seidel - 1992
23 Triangulating a nonconvex polytope (context) - Chazelle, Palios - 1990
20 An efficient algorithm for finding the CSG representation of.. - Dobkin, Guibas et al. - 1993
15 Upper bounds on geometric permutations for convex sets (context) - Wenger - 1990
11 A polyhedral representation for computer vision (context) - Baumgart - 1975
8 A theorem on arrangements of lines in the plane (context) - Canham - 1969
7 the power of non-rectilinear holes (context) - Lingas - 1982
7 the maximal number of edges of many faces in an arrangement (context) - Edelsbrunner, Welzl - 1986
6 Tetrahedral mesh generation in polyhedral regions based on c.. (context) - Joe - 1994
5 Triangulation and CSG representation of polyhedra with arbit.. (context) - Dey - 1991
4 Horizon theorems for lines and polygons (context) - Bern, Eppstein et al. - 1991
3 Sorting Jordan sequences in linear time (context) - Hoffmann, Mehlhorn et al. - 1986
1 An introduction ot the theory of numbers (context) - Hardy, Wright - 1979
1 On disjoint concave chains in arrangements of pseudolines - Halperin, Sharir - 1991

Documents on the same site (http://www.cs.ubc.ca/spider/snoeyink/papers/papers.html): More
Folding Rulers inside Triangles - van Kreveld, Snoeyink, Whitesides (1996) (Correct)
Efficiently Planning Compliant Motion In The Plane - Friedman, Hershberger, Snoeyink (1996) (Correct)
Cartographic Line Simplification and Polygon CSG Formulae.. - Hershberger, Snoeyink (1998) (Correct)

Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents