Steven Fortune  Home/Search
Context Related
| belllabs.com/cm/cs/wh...compgeom.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: belllabs.com/cm/cs/who/sj...pubs (more) Homepages: S.Fortune [2] HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: Computational geometry, the study of algorithms involving relatively simple geometric objects, is an active, exciting field. This chapter samples current research in computational geometry. Three topics are discussed at some length: the theory of arrangements, a random-incremental convex hull algorithm, and robustness of geometric algorithms. 1 Introduction As pointed out by Robin Forrest and others[39, 79], the term "computational geometry" could be used for a variety of fields,... (Update)
Context of citations to this paper: More
.... researchers in this field have begun to address the efficacy of the algorithms, the issues concerning robustness and numerical stability[25, 49], and the actual running times of their implementions. In this and the following chapter we concentrate mostly on the theoretical...
...the point is discarded. These algorithms have been implemented. In practice, their running times are competitive with other algorithms [24]. We can compare Quickhull with the randomized incremental algorithms by changing the selection step of Quickhull. If Quickhull selects a...
Cited by: More
The Quickhull Algorithm for Convex Hulls - Barber, Dobkin, Huhdanpaa (1996) (Correct)
Computational Geometry - Lee (1996) (Correct)
Computational Geometry I - Lee (1996) (Correct)
Active bibliography (related documents): More All
1.4: Voronoi Diagrams and Delaunay Triangulations - Fortune (1992) (Correct)
1.1: Backwards Analysis of Randomized Geometric Algorithms - Seidel (1992) (Correct)
0.7: Numerical Stability of Algorithms for Line Arrangements - Fortune, Milenkovic (1991) (Correct)
Users who viewed this document also viewed: More All
0.2: Lecture Notes on Delaunay Mesh Generation - Shewchuk (1999) (Correct)
0.1: Efficient Algorithms for Geometric Optimization - Agarwal, Sharir (1998) (Correct)
0.1: Mesh Generation - Bern, Plassmann (2000) (Correct)
Similar documents based on text: More All
0.0: Gambling Systems and Multiplication-Invariant Measures - By Jeffrey (Correct)
0.0: Generalizations of Bold Play in Red and Black - Marcus Pendergrass Huntsville (Correct)
0.0: Learning Patterns from Unix Process Execution Traces for.. - Lee, Stolfo (1997) (Correct)
Related documents from co-citation: More All
3: How good are convex hull algorithms - Avis, Bremner et al. - 1997
3: Applications of random sampling in computational geometry - Clarkson, Shor - 1989
2: Triangulating a Simple Polygon in Linear Time (context) - Chazelle - 1991
BibTeX entry: (Update)
S. Fortune, "Computational Geometry," in Directions in Computational Geometry, R. Martin, Ed., Information Geometers, 1993. http://citeseer.nj.nec.com/fortune94computational.html More
@misc{ fortune93computational,
author = "S. Fortune and C. Geometry and i Directions",
title = "in Computational Geometry",
text = "S. Fortune, Computational Geometry, in Directions in Computational Geometry,
R. Martin, Ed., Information Geometers, 1993.",
year = "1993",
url = "citeseer.nj.nec.com/fortune94computational.html" }
Citations (may not include all citations):1643 The Art of Computer Programming (context) - Knuth - 1969
429 Algorithms in Combinatorial Geometry (context) - Edelsbrunner - 1987
420 Computational Geometry (context) - Preparata, Shamos - 1985
272 Applications of random sampling in computational geometry - Clarkson, Shor - 1989
223 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
203 Voronoi diagrams -- a survey of a fundamental geometric data.. (context) - Aurenhammer - 1991
155 Methods and Applications of Interval Analysis (context) - Moore - 1979
124 Art Gallery Theorems and Algorithms (context) - O'Rourke - 1987
124 A sweepline algorithm for Voronoi diagrams (context) - Fortune - 1987
122 Simulation of simplicity: a technique to cope with degenerat.. - Edelsbrunner, Mucke - 1990
111 Numerical Methods (context) - Dahlquist, Bjorck et al. - 1974
96 Convex Polytopes (context) - Grunbaum - 1967
92 Combinatorial complexity bounds for arrangements of curves a.. (context) - Clarkson, Edelsbrunner et al. - 1990
86 Linear programming and convex hulls made easy (context) - Seidel - 1990
85 Randomized incremental construction of Delaunay and Voronoi .. (context) - Guibas, Knuth et al. - 1990
80 New applications of random sampling in computational geometr.. - Clarkson - 1987
69 Constructing arrangements of lines and hyperplanes with appl.. (context) - Edelsbrunner, O'Rourke et al. - 1986
67 Efficient partition trees (context) - Matousek - 1991
66 Verifiable implementations of geometric algorithms using fin.. (context) - Milenkovic - 1988
66 Verifiable Implementations of Geometric Algorithms using Fin.. (context) - Milenkovic - 1988
61 An efficient algorithm for determining the convex hull of a .. (context) - Graham - 1972
56 The power of geometric duality (context) - Chazelle, Guibas et al. - 1983
54 Epsilon geometry: building robust algorithms from imprecise .. (context) - Salesin, Stolfi et al. - 1989
54 Cambridge University Press (context) - Bjoerner, Vergnas et al. - 1992
53 A geometric consistency theorem for a symbolic perturbation .. (context) - Yap - 1990
52 Finite-resolution computational geometry (context) - Greene, Yao - 1986
47 Backwards analysis of randomized geometric algorithms - Seidel
42 Four results on randomized incremental constructions - Clarkson, Mehlhorn et al. - 1992
37 The complexity and construction of many faces in arrangement.. (context) - Edelsbrunner, Guibas et al. - 1990
36 Efficient Delaunay triangulation using rational arithmetic (context) - Karasick, Lieber et al. - 1990
36 Voronoi diagrams and Delaunay triangulations - Fortune
34 Higher-dimensional Voronoi diagrams in linear expected time (context) - Dwyer - 1991
34 Double precision geometry: a general technique for calculati.. - Milenkovic - 1989
33 The problems of accuracy and robustness in geometric computa.. (context) - Hoffmann - 1989
32 Using tolerances to guarantee valid polyhedral modeling resu.. (context) - Segal - 1990
32 A general approach to removing degeneracies - Emiris, Canny - 1991
32 Stable maintenance of point-set triangulation in two dimensi.. (context) - Fortune - 1989
31 Convex Polytopes and the Upper Bound Conjecture (context) - McMullen, Shephard - 1971
31 Computing Dirichlet tessellations in the plane (context) - Green, Sibson - 1977
30 Towards implementing robust geometric computations (context) - Hoffmann, Hopcroft et al. - 1988
29 Robust set operations on polyhedral solids (context) - Hoffmann, Hopcroft et al. - 1989
28 A floating-point technique for extending the available preci.. (context) - Dekker - 1971
28 Representing geometric structures in d dimensions: topology .. (context) - Brisson - 1989
27 An acyclicity theorem for cell complexes in d dimensions (context) - Edelsbrunner
26 Constructing strongly convex hulls using exact or rounded ar.. - Li, Milenkovic - 1990
25 Symbolic treatment of geometric degeneracies (context) - Yap - 1990
25 the zone theorem for hyperplane arrangements (context) - Edelsbrunner, Seidel et al. - 1990
23 Computational geometry in a curved world (context) - Dobkin, Souvaine - 1990
22 Numerical stability of algorithms for line arrangements - Fortune, Milenkovic - 1991
22 The Universality theorems on the classification problem of c.. (context) - Mnev - 1989
20 Randomized parallel algorithms for trapezoidal diagrams - Clarkson, Cole et al. - 1991
19 Construction of the Voronoi diagram for one million generato.. (context) - Sugihara, Iri - 1989
19 the zone of a surface in a hyperplane arrangement - Aronov, Pellegrini et al. - 1991
19 Voronoi diagrams and arrangements (context) - Edelsbrunner, Seidel - 1986
18 An optimal convex hull algorithm and new results on cuttings (context) - Chazelle - 1991
18 Intersection and decomposition algorithms for planar arrange.. (context) - Agarwal - 1991
18 Randomized geometric algorithms - Clarkson
17 the sum of squares of cell complexities in hyperplane arrang.. - Aronov, Matousek et al. - 1991
16 Intersection queries for curved objects (context) - Agarwal, van Kreveld et al. - 1991
16 Finding compact coordinate representations for polygons and .. - Milenkovic, Nackman - 1990
16 A solid modeling system free from topological inconsistency (context) - Sugihara, Iri - 1989
16 An Introduction to Convex Polytopes (context) - Brndsted - 1983
15 Lines in space -- combinatorics (context) - Chazelle, Edelsbrunner et al. - 1989
15 Triangles in space or building (context) - Aronov, Sharir - 1990
14 Algorithmic and Geometric Aspects of Robotics (context) - Schwartz, Yap - 1987
13 Oriented projective geometry (context) - Stolfi - 1987
12 Rounding face lattices in the plane (context) - Milenkovic - 1989
12 the representation and manipulation of rigid solids (context) - Karasick - 1988
11 Rounding face lattices in d dimensions (context) - Milenkovic - 1990
10 Geometric algorithms in finite-precision arithmetic (context) - Sugihara, Iri - 1988
10 The complexity of many cells in arrangements of planes and r.. (context) - Edelsbrunner, Guibas et al. - 1990
9 Random approximation of convex sets (context) - Schneider - 1988
7 dimensional spaces and n-dimensional generalized maps (context) - Lienhardt, n- - 1989
6 Robust Algorithms in a Program Library for Geometric Computa.. (context) - Schorn - 1991
5 Numerical stability of algorithms for Delaunay triangulation.. (context) - Fortune - 1992
5 A probabilistic algorithm for the post office problem (context) - Clarkson - 1985
4 The implementation of an algorithm to find the convex hull o.. (context) - Day - 1990
4 Upper bounds for configurations and polytopes in R d (context) - Goodman, Pollack - 1986
4 American Mathematical Society (context) - Grunbaum, Spreads et al. - 1972
4 gentler average-case analysis for convex hulls and maximal v.. (context) - Dwyer - 1990
3 How to reduce the average complexity of convex hull finding .. (context) - Devroye - 1981
3 A fast planar partition algorithm: part (context) - Mulmuley - 1988
3 Recipes for geometry and numerical analysis--part I: an empi.. (context) - Dobkin, Silver - 1988
2 Fundamental Algorithms for Computer Graphics (context) - Forrest, in - 1985
2 A fast planar partition algorithm: part II (context) - Mulmuley - 1989
2 Applications of random sampling to online algorithms in comp.. (context) - Boissonnat, Devillers et al. - 1990
1 and real matroids (context) - Alon, of et al. - 1986
1 Convex hulls of points sets in two and three dimensions (context) - Preparata, Hong - 1977
1 Stretchability of pseudoline arrangements is NP-hard (context) - Shor - 1991
1 New Trends in Discrete and Computational Geometry (context) - Guibas, Sharir et al.
1 Analysis of a simple yet efficient convex hull algorithm (context) - Golin, Sedgewick - 1988
1 Closest-point problemsProc (context) - Shamos, Hoey - 1975
Documents on the same site (http://cm.bell-labs.com/cm/cs/who/sjf/pubs.html): More
Topological beam tracing - Fortune (1999) (Correct)
Robustness issues in geometric algorithms - Fortune (1996) (Correct)
Static Analysis Yields Efficient Exact Integer Arithmetic.. - Fortune, Van Wyk (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