Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, Paul J. Tannenbaum  Home/Search
Context Related
| jhu.edu/~goodrich/pubs/snap.ps jhu.edu/~goodrich/pubs/snap.ps arl.mil/~pjt/publications/socg97.ps Cached: PS.gz PS PDF DjVu Image Update Help From: jhu.edu/~goodrich/pubs/ (more) From: arl.mil/~pjt/publications Homepages: M.Goodrich [2] [3] L.Guibas J.Hershberger HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: We study the problem of robustly rounding a set S of n line segments in R 2 using the snap rounding paradigm. In this paradigm each pixel containing an endpoint or intersection point is called "hot," and all segments intersecting a hot pixel are re-routed to pass through its center. We show that a snap-rounded approximation to the arrangement defined by S can be built in an output-sensitive fashion, and that this can be done without first determining all the intersecting pairs of segments in... (Update)
Context of citations to this paper: More
...under insertion and deletion of edges; they also give elementary proofs of basic topological properties of snap rounding. Goodrich et al. [7] give improved algorithms to snap round a set of intersecting edges, in the case when there are many intersections within a pixel....
...floating point arithmetic. Some examples of previous and related work on robust floating point geometric algorithms can be found in [17], 18] 22] 27] 32] and [33] Our motivating application is geometric modeling of molecules. Our software package is part of a toolbox...
Cited by: More
Hardware-Assisted Computation of Depth Contours - Krishnan, Mustafa.. (Correct)
Rounding Arrangements Dynamically - Guibas, Marimont (1995) (Correct)
Two-Dimensional Arrangements in CGAL and Adaptive Point.. - Hanniel, Halperin (2000) (Correct)
Active bibliography (related documents): More All
0.8: Backwards Analysis of Randomized Geometric Algorithms - Seidel (1992) (Correct)
0.7: Computational Geometry - Fortune (1994) (Correct)
0.3: Classical Computational Geometry in GeomNet - Barequet, Bridgeman, Duncan.. (1997) (Correct)
Similar documents based on text: More All
0.3: The Number of Edges of Many Faces in a Line Segment.. - Aronov, Edelsbrunner, .. (1992) (Correct)
0.2: Kinetic Collision Detection Between Two Simple Polygons - Basch, Erickson, Guibas, .. (1999) (Correct)
0.2: Kinetic Data Structures: Animating Proofs Through Time - Julien Basch (Correct)
Related documents from co-citation: More All
6: Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithm.. (context) - Milenkovic - 1988
6: Finite-Resolution Computational Geometry (context) - Greene - 1986
5: Rounding arrangements dynamically - Guibas, Marimont - 1995
BibTeX entry: (Update)
M. Goodrich, L. J. Guibas, J. Hershberger, and P. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proceedings of the Thirteenth Annual ACM Symposium on Computational Geometry, pages 284--293, 1997. http://citeseer.nj.nec.com/goodrich97snap.html More
@inproceedings{ goodrich97snap,
author = "Michael T. Goodrich and Leonidas J. Guibas and John Hershberger and Paul J. Tanenbaum",
title = "Snap Rounding Line Segments Efficiently in Two and Three Dimensions",
booktitle = "Symposium on Computational Geometry",
pages = "284-293",
year = "1997",
url = "citeseer.nj.nec.com/goodrich97snap.html" }
Citations (may not include all citations):216 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
133 Algorithms for reporting and counting geometric intersection.. (context) - Bentley, Ottmann - 1979
118 Simulation of simplicity: a technique to cope with degenerat.. - Edelsbrunner, Mucke - 1990
84 Randomized incremental construction of Delaunay and Voronoi .. (context) - Guibas, Knuth et al. - 1992
62 On range searching with semialgebraic sets - Agarwal, Matousek - 1994
53 Epsilon geometry: building robust algorithms from imprecise .. (context) - Guibas, Salesin et al. - 1989
50 Finite-resolution computational geometry (context) - Greene, Yao - 1986
47 Backwards analysis of randomized geometric algorithms - Seidel - 1993
41 Four results on randomized incremental constructions - Clarkson, Mehlhorn et al. - 1993
34 Double precision geometry: a general technique for calculati.. - Milenkovic - 1989
28 Towards implementing robust geometric computations (context) - Hoffmann, Hopcroft et al. - 1988
25 Numerical stability of algorithms for 2-d Delaunay triangula.. (context) - Fortune - 1995
25 Rounding arrangements dynamically - Guibas, Marimont - 1995
21 Numerical stability of algorithms for line arrangements - Fortune, Milenkovic - 1991
18 Randomized geometric algorithms - Clarkson - 1992
15 Evaluation of a new method to compute signs of determinants (context) - Avnaim, Boissonnat et al. - 1995
13 Robust proximity queries in implicit Voronoi diagrams - Liotta, Preparata et al. - 1996
11 Practical segment intersection with finite precision output - Hobby - 1993
9 Geometric algorithms in finite-precision arithmetic (context) - Sugihara, Iri - 1988
6 Two design principles of geometric algorithms in finite-prec.. (context) - Sugihara, Iri - 1989
5 Algorithms for reporting and counting geometric intersection.. (context) - Brown - 1981
3 A fast planar partition algorithm: part (context) - Mulmuley - 1988
2 A tail estimate for Mulmuley's segment intersection algorith.. (context) - Matousek, Seidel - 1992
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.cs.jhu.edu/~goodrich/pubs/): More
Dynamic Trees and Dynamic Point Location - Goodrich, Tamassia (1991) (Correct)
On the Complexity of Optimization Problems for 3-Dimensional.. - Das, Goodrich (1995) (Correct)
Bounded-Independence Derandomization of Geometric.. - Goodrich, Ramos (1996) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute