Giuseppe Liotta, Franco P. Preparata, Roberto Tamassia  Home/Search
Context Related
| 151.100.16.20/pub/Theory...robust.ps.gz dis.uniroma1.it/pub/Theo...robust.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: fermivista.math.j...151.100.16.20 (more) Homepages: G.Liotta F.Preparata R.Tamassia HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, as a worst-case quantification of the precision (number of bits) to which arithmetic calculation have to be executed in order to guarantee topological correctness. We also propose a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm and an illustration of... (Update)
Context of citations to this paper: More
...However, reducing the degree of an algorithm may increase its time complexity in the Real RAM model. Following Liotta et al. [13], we consider the degree of the predicates as an additional measure of the complexity of problems and algorithms, and intend to elucidate...
...contributions can be summarized as follows. i) As an additional measure of eoeectiveness for a checker, we adopt the notion of degree [19,18,5], which takes into account the number of bits required by the checker to carry out error free computations. A good checker should have...
Cited by: More
Reporting Intersections among Thick Objects - Vigneron (2002) (Correct)
Efficient algorithms for line and curve segment.. - Boissonnat, Snoeyink (1999) (Correct)
Checking the Convexity of Polytopes and the.. - Devillers.. (1998) (Correct)
Similar documents (at the sentence level):
64.1%: Robust Proximity Queries in Implicit Voronoi Diagrams - Liotta, Preparata, Tamassia (1996) (Correct)
Active bibliography (related documents): More All
0.3: Robust plane sweep for intersecting segments - Boissonnat, Preparata (1997) (Correct)
0.2: Shapes And Implementations In Three-Dimensional Geometry - Mücke (1993) (Correct)
0.2: Robustness Issues in Computational Geometry - Keyser (Correct)
Similar documents based on text: More All
0.1: Graph Drawing '93 - Di Battista, Eades, de Fraysseix.. (1993) (Correct)
0.1: Spirality And Optimal Orthogonal Drawings - Di Battista, Liotta, Vargiu (1998) (Correct)
0.1: Checking the Convexity of Polytopes and the Planarity of.. - Devillers, al. (1998) (Correct)
Related documents from co-citation: More All
16: Checking geometric programs or verification of geometric structures - Mehlhorn, Naher et al. - 1996
13: Algorithms for reporting and counting geometric intersections (context) - Bentley, Ottmann - 1979
12: line convex planarity testing - Di Battista, Tamassia et al. - 1994
BibTeX entry: (Update)
G. Liotta, F. P. Preparata, and R. Tamassia. Robust proximity queries: An illustration of degree-driven algorithm design. SIAM J. Computing, to appear. http://www.cs.brown.edu/cgc/papers/lpt-rpqid-.ps.gz. http://citeseer.nj.nec.com/104793.html More
@inproceedings{ liotta97robust,
author = "Giuseppe Liotta and Franco P. Preparata and Roberto Tamassia",
title = "Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design",
booktitle = "Symposium on Computational Geometry",
pages = "156-165",
year = "1997",
url = "citeseer.nj.nec.com/104793.html" }
Citations (may not include all citations):1102 Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
219 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
134 Optimal search in planar subdivisions (context) - Kirkpatrick - 1983
102 Planar point location using persistent search trees (context) - Sarnak, Tarjan - 1986
100 Optimal point location in a monotone subdivision (context) - Edelsbrunner, Guibas et al. - 1986
85 Randomized incremental construction of Delaunay and Voronoi .. (context) - Guibas, Knuth et al. - 1992
68 Fast detection of polyhedral intersection (context) - Dobkin, Kirkpatrick - 1983
50 Efficient exact arithmetic for computational geometry - Fortune, Van Wyk - 1993
44 Location of a point in a planar subdivision and its applicat.. (context) - Lee, Preparata - 1977
36 Exact geometric computation in LEDA - Burnikel, Konnemann et al. - 1995
35 Efficient Delaunay triangulations using rational arithmetic (context) - Karasick, Lieber et al. - 1991
34 Primitives for the manipulation of three-dimensional subdivi.. (context) - Dobkin, Laszlo - 1989
32 The problems of accuracy and robustness in geometric computa.. (context) - Hoffmann - 1989
32 On degeneracy in geometric computations (context) - Burnikel, Mehlhorn et al. - 1994
31 Stable maintenance of point set triangulations in two dimens.. (context) - Fortune - 1989
26 Safe and effective determinant evaluation - Clarkson - 1992
26 A new approach to planar point location (context) - Preparata - 1981
25 Symbolic treatment of geometric degeneracies (context) - Yap - 1990
17 Exact Computation of Voronoi Diagrams and Line Segment Inter.. (context) - Burnikel - 1996
12 Efficient point location in a convex spatial cell-complex (context) - Preparata, Tamassia - 1992
10 one million (context) - Sugihara, Iri et al. - 1992
10 How to search in history (context) - Chazelle - 1985
8 Optimal cooperative search in fractional cascaded data struc.. - Tamassia, Vitter - 1996
8 Computational geometry and computer graphics - Dobkin - 1992
8 Finding extreme points in three dimensions and solving the p.. (context) - Edelsbrunner, Maurer - 1985
7 Computational Geometry: Theory and Applications (context) - Yap, geometric
4 Introduction to higher algebra (context) - Bocher - 1907
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://fermivista.math.jussieu.fr/ftp/151.100.16.20.html): More
Visual Query Systems: A Taxonomy - Batini, Catarci, Costabile, Levialdi (1992) (Correct)
Multi-Dimensional Interval Routing Schemes - Flammini, Gambosi, Nanni, Tan (1995) (Correct)
An algorithm for the nonlinear programming problem of the.. - Di Pillo (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