Steven Fortune, Victor Milenkovic  Home/Search
Context Related
| miami.edu/~vjm/Papers/scg91.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: miami.edu/~vjm/papers (more) Homepages: S.Fortune [2] V.Milenkovic HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: We analyze the behavior of two line arrangement algorithms, a sweepline algorithm and an incremental algorithm, in approximate arithmetic. The algorithms have running times O(n 2 log n) and O(n 2 ) respectively. We show that each of these algorithms can be implemented to have O(nffl) relative error. This means that each algorithm produces an arrangement realized by a set of pseudolines so that each pseudoline differs from the corresponding line relatively by at most O(nffl). We also show... (Update)
Context of citations to this paper: More
...point arithmetic is a di#cult task even if robustness only means that the program should always run to completion. The papers [FM91, Mil88, SOI90] illustrate the di#culty of designing robust algorithms. Second, the repair step is non trivial if the floating point algorithm...
...types of error in numeric computations. Such errors has been studied, for example, in the context of computational geometry [8, 9, 13, 14, 21, 22, 23]. We discuss this further in Section 6. Approximate sorting. Bern, Karloff, Raghavan, and Schieber [3] introduced approz...
Cited by: More
Trends and Developments in Computational Geometry - de Berg (1995) (Correct)
The LEDA class real number - Christoph Burnikel Kurt (1996) (Correct)
Approximate Data Structures (Extended Abstract) - Matias, Vitter, Young (1994) (Correct)
Active bibliography (related documents): More All
0.7: Computational Geometry - Fortune (1994) (Correct)
0.5: Double Precision Geometry: A General Technique for Calculating.. - Milenkovic (1989) (Correct)
0.3: Robust Polygon Modeling - Milenkovic (1993) (Correct)
Similar documents based on text: More All
0.4: On Generalized Geometric Graphs and Pseudolines - Sharir, Smorodinsky (2001) (Correct)
0.4: A Generalised Sweep-Line Method for Safety Properties - Kristensen, Mailund (2002) (Correct)
0.4: Analysing Infinite-State Systems by Combining Equivalence.. - Mailund (2002) (Correct)
Related documents from co-citation: More All
16: Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithm.. (context) - Milenkovic - 1988
11: Epsilon geometry: Building robust algorithms from imprecise computations (context) - Guibas, Salesin et al. - 1989
11: Double precision geometry: a general technique for calculating line and segment .. - Milenkovic - 1989
BibTeX entry: (Update)
FORTUNE, S., AND MILENKOVIC, V. Numerical stability of algorithms for line arrangements. In Proc. 7th Annu. ACM Sympos. Comput. Geom. (1991), pp. 334--341. http://citeseer.nj.nec.com/fortune91numerical.html More
@inproceedings{ fortune91numerical,
author = "Steven Fortune and Victor Milenkovic",
title = "Numerical Stability of Algorithms for Line Arrangements",
booktitle = "Symposium on Computational Geometry",
pages = "334-341",
year = "1991",
url = "citeseer.nj.nec.com/fortune91numerical.html" }
Citations (may not include all citations):216 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
87 Topological Graph Theory (context) - Gross, Tucker - 1987
68 Constructing Arrangements of Lines and Hyperplanes with Appl.. (context) - Edelsbrunner, O'Rourke et al. - 1983
65 Verifiable Implementations of Geometric Algorithms using Fin.. (context) - Milenkovic - 1988
65 Verifiable implementations of geometric algorithms using fin.. (context) - Milenkovic - 1988
53 Epsilon Geometry: Building Robust Algorithms from Imprecise .. (context) - Guibas, Salesin et al. - 1989
34 Double Precision Geometry: A General Technique for Calculati.. - Milenkovic - 1989
32 The Problems of Accuracy and Robustness in Geometric Computa.. (context) - Hoffmann - 1989
28 Towards Implementing Robust Geometric Computations (context) - Hoffmann, Hopcroft et al. - 1988
25 Constructing Strongly Convex Hulls using Exact or Rounded Ar.. - Li, Milenkovic - 1990
22 The Universality theorems on the classification problem of c.. (context) - Mnev - 1989
18 Construction of the Voronoi Diagram for One Million Generato.. (context) - Sugihara, Iri - 1989
16 A Paradigm for Robust Geometric Algorithms (context) - Hopcroft, Kahn - 1989
12 the Representation and Manipulation of Rigid Solids (context) - Karasick - 1988
9 Geometric Algorithms in FinitePrecision Arithmetic (context) - Sugihara, Iri - 1988
4 American Mathematical Society (context) - Grunbaum, Spreads et al. - 1972
3 th Annual Symposium on the Foundations of Computer Science (context) - Chazelle, Guibas et al. - 1983
1 Topologically Sweeping and Arrangement Proceedings of the Sy.. (context) - Edelsbrunner, Guibas - 1986
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.cs.miami.edu/~vjm/papers.html): More
Rotational Polygon Overlap Minimization and Compaction - Milenkovic (1998) (Correct)
Column-Based Strip Packing using Ordered and Compliant.. - Karen Daniels (1996) (Correct)
Multiple Translational Containment Part I: An Approximate.. - Daniels, Milenkovic (1995) (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