Concepedia

Output-sensitive Algorithms

Output-Sensitive Algorithms is an algorithmic paradigm in computational geometry that belongs to the class of algorithms whose runtime complexity is characterized not only by the size of the input but explicitly in addition by the size of the output, thereby distinguishing it from traditional algorithms that depend solely on input parameters.

97

Publications

3.8K

Citations

173

Authors

97

Institutions

Publications per year

2017–2026

6

Parents

Publications

97

An Output-Sensitive Algorithm for Computing Visibility Graphs

Subir Ghosh, David M. Mount · SIAM Journal on Computing · 1991 · 248 citations

, , +12

BD-tree

Doug L. James, Dinesh K. Pai · ACM Transactions on Graphics · 2004 · 206 citations

, , +13

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries

Erik D. Demaine, Jeff Erickson, John Iacono et al. · Discrete & Computational Geometry · 2005 · 168 citations · Full text

, , +7

The randomized z-buffer algorithm

Michael Wand, Matthias Fischer, Ingmar Peter et al. · 2001 · 127 citations

, , +16

Output-sensitive results on convex hulls, extreme points, and related problems

Timothy M. Chan · Discrete & Computational Geometry · 1996 · 102 citations · Full text

, , +15

1–5 of 97

Authors

173

  1. TM
    Timothy M. Chan

    University of Waterloo, Canada

    5 publications · 241 citations

    5

    h-index

  2. MO
    M.H. Overmars

    Utrecht University, Netherlands

    4 publications · 56 citations

    4

    h-index

  3. MT
    Michael T. Goodrich

    Johns Hopkins University, United States

    4 publications · 92 citations

    4

    h-index

  4. SH
    Sariel Har-Peled

    University of Illinois Urbana-Champaign, United States

    3 publications · 62 citations

    3

    h-index

  5. MK
    Michael Kerber

    Institute of Science and Technology Austria, Austria

    3 publications · 150 citations

    3

    h-index

1–5 of 173

Institutions

97

  1. Tel Aviv University

    Tel Aviv, Israel

    6 h-index

    9 publications

    202 citations

  2. University of British Columbia

    Vancouver, Canada

    5 h-index

    7 publications

    362 citations

  3. New York University

    New York, United States

    5 h-index

    7 publications

    378 citations

  4. Utrecht University

    Utrecht, The Netherlands

    5 h-index

    12 publications

    238 citations

  5. University of Waterloo

    Waterloo, Canada

    4 h-index

    4 publications

    110 citations

  6. Institut national de recherche en sciences et technologies du numérique

    Le Chesnay-Rocquencourt, France

    4 h-index

    9 publications

    437 citations

  7. Johns Hopkins University

    Baltimore, United States

    4 h-index

    6 publications

    112 citations

  8. Simon Fraser University

    Burnaby, Canada

    3 h-index

    5 publications

    65 citations

1–8 of 97

Venues

  1. Symposium on Discrete Algorithms

    Conference · 5 publications · 112 citations

    5

    h-index

  2. SIAM Journal on Computing

    5 publications · 375 citations

    5

    h-index

  3. ACM Transactions on Graphics

    TOG · 4 publications · 343 citations

    4

    h-index

  4. Discrete & Computational Geometry

    4 publications · 356 citations

    4

    h-index

  5. IEEE Transactions on Visualization and Computer Graphics

    TVCG · 3 publications · 108 citations

    3

    h-index

1–5