---
_id: '18778'
abstract:
- lang: eng
  text: Given a point set P in the d-dimensional unit hypercube, we give upper bounds
    on the maximal expected number of extreme points when each point is perturbed
    by small random noise chosen independently for each point from the same noise
    distribution Δ. Our results are parametrized by the variance of the noise
    distribution. For large variance we essentially consider the average case for
    distribution Δ while for variance 0 we consider the worst case. Hence our
    results give upper bounds on the number of extreme points where our input distributions
    range from average case to worst case.<br>Our main contribution is a rather general
    lemma that can be used to obtain upper bounds on the expected number of extreme
    points for a large class of noise distributions. We then apply this lemma to obtain
    explicit bounds for random noise coming from the Gaussian normal distribution
    of variance &#963;² and the uniform distribution in a hypercube of side length
    &epsilon. For these noise distributions we show upper bounds of O( (1/ &#963;
    )^d * log^3/2 * d - 1 n ) and O( ( (n log n) / &#949; )^d/(d+1) ), respectively.
    Besides its theoretical motivation our model is also motivated by the observation
    that in many applications of convex hull algorithms the input data is inherently
    noisy, e.g. when the data comes from physical measurement or imprecise arithmetic
    is used.
author:
- first_name: Valentina
  full_name: Damerow, Valentina
  last_name: Damerow
- first_name: Christian
  full_name: Sohler, Christian
  last_name: Sohler
citation:
  ama: 'Damerow V, Sohler C. Extreme Points Under Random Noise. In: <i>Proceedings
    of the 12th European Symposium on Algorithms (ESA’04)</i>. Berlin, Heidelberg;
    2004. doi:<a href="https://doi.org/10.1007/978-3-540-30140-0_25">10.1007/978-3-540-30140-0_25</a>'
  apa: Damerow, V., &#38; Sohler, C. (2004). Extreme Points Under Random Noise. In
    <i>Proceedings of the 12th European Symposium on Algorithms (ESA’04)</i>. Berlin,
    Heidelberg. <a href="https://doi.org/10.1007/978-3-540-30140-0_25">https://doi.org/10.1007/978-3-540-30140-0_25</a>
  bibtex: '@inproceedings{Damerow_Sohler_2004, place={Berlin, Heidelberg}, title={Extreme
    Points Under Random Noise}, DOI={<a href="https://doi.org/10.1007/978-3-540-30140-0_25">10.1007/978-3-540-30140-0_25</a>},
    booktitle={Proceedings of the 12th European Symposium on Algorithms (ESA’04)},
    author={Damerow, Valentina and Sohler, Christian}, year={2004} }'
  chicago: Damerow, Valentina, and Christian Sohler. “Extreme Points Under Random
    Noise.” In <i>Proceedings of the 12th European Symposium on Algorithms (ESA’04)</i>.
    Berlin, Heidelberg, 2004. <a href="https://doi.org/10.1007/978-3-540-30140-0_25">https://doi.org/10.1007/978-3-540-30140-0_25</a>.
  ieee: V. Damerow and C. Sohler, “Extreme Points Under Random Noise,” in <i>Proceedings
    of the 12th European Symposium on Algorithms (ESA’04)</i>, 2004.
  mla: Damerow, Valentina, and Christian Sohler. “Extreme Points Under Random Noise.”
    <i>Proceedings of the 12th European Symposium on Algorithms (ESA’04)</i>, 2004,
    doi:<a href="https://doi.org/10.1007/978-3-540-30140-0_25">10.1007/978-3-540-30140-0_25</a>.
  short: 'V. Damerow, C. Sohler, in: Proceedings of the 12th European Symposium on
    Algorithms (ESA’04), Berlin, Heidelberg, 2004.'
date_created: 2020-09-01T12:26:47Z
date_updated: 2022-01-06T06:53:52Z
department:
- _id: '63'
doi: 10.1007/978-3-540-30140-0_25
language:
- iso: eng
place: Berlin, Heidelberg
publication: Proceedings of the 12th European Symposium on Algorithms (ESA'04)
publication_identifier:
  isbn:
  - '9783540230250'
  - '9783540301400'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
status: public
title: Extreme Points Under Random Noise
type: conference
user_id: '15415'
year: '2004'
...
---
_id: '18263'
abstract:
- lang: eng
  text: We generalize univariate multipoint evaluation of polynomials of degree n
    at sublinear amortized cost per point. More precisely, it is shown how to evaluate
    a bivariate polynomial p of maximum degree less than n, specified by its n^2 coefficients,
    simultaneously at n^2 given points using a total of O(n^2.667) arithmetic operations.
    In terms of the input size N being quadratic in n, this amounts to an amortized
    cost of O(N^0.334) per point.
author:
- first_name: Michael
  full_name: Nüsken, Michael
  last_name: Nüsken
- first_name: Martin
  full_name: Ziegler, Martin
  last_name: Ziegler
citation:
  ama: 'Nüsken M, Ziegler M. Fast Multipoint Evaluation of Bivariate Polynomials.
    In: <i>Proc. 12th Annual Symposium on Algorithms (ESA’04)</i>. Vol 3221. Berlin,
    Heidelberg: Springer; 2004:544-555. doi:<a href="https://doi.org/10.1007/978-3-540-30140-0_49">10.1007/978-3-540-30140-0_49</a>'
  apa: 'Nüsken, M., &#38; Ziegler, M. (2004). Fast Multipoint Evaluation of Bivariate
    Polynomials. In <i>Proc. 12th Annual Symposium on Algorithms (ESA’04)</i> (Vol.
    3221, pp. 544–555). Berlin, Heidelberg: Springer. <a href="https://doi.org/10.1007/978-3-540-30140-0_49">https://doi.org/10.1007/978-3-540-30140-0_49</a>'
  bibtex: '@inproceedings{Nüsken_Ziegler_2004, place={Berlin, Heidelberg}, title={Fast
    Multipoint Evaluation of Bivariate Polynomials}, volume={3221}, DOI={<a href="https://doi.org/10.1007/978-3-540-30140-0_49">10.1007/978-3-540-30140-0_49</a>},
    booktitle={Proc. 12th Annual Symposium on Algorithms (ESA’04)}, publisher={Springer},
    author={Nüsken, Michael and Ziegler, Martin}, year={2004}, pages={544–555} }'
  chicago: 'Nüsken, Michael, and Martin Ziegler. “Fast Multipoint Evaluation of Bivariate
    Polynomials.” In <i>Proc. 12th Annual Symposium on Algorithms (ESA’04)</i>, 3221:544–55.
    Berlin, Heidelberg: Springer, 2004. <a href="https://doi.org/10.1007/978-3-540-30140-0_49">https://doi.org/10.1007/978-3-540-30140-0_49</a>.'
  ieee: M. Nüsken and M. Ziegler, “Fast Multipoint Evaluation of Bivariate Polynomials,”
    in <i>Proc. 12th Annual Symposium on Algorithms (ESA’04)</i>, 2004, vol. 3221,
    pp. 544–555.
  mla: Nüsken, Michael, and Martin Ziegler. “Fast Multipoint Evaluation of Bivariate
    Polynomials.” <i>Proc. 12th Annual Symposium on Algorithms (ESA’04)</i>, vol.
    3221, Springer, 2004, pp. 544–55, doi:<a href="https://doi.org/10.1007/978-3-540-30140-0_49">10.1007/978-3-540-30140-0_49</a>.
  short: 'M. Nüsken, M. Ziegler, in: Proc. 12th Annual Symposium on Algorithms (ESA’04),
    Springer, Berlin, Heidelberg, 2004, pp. 544–555.'
date_created: 2020-08-25T11:25:11Z
date_updated: 2022-01-06T06:53:28Z
department:
- _id: '63'
doi: 10.1007/978-3-540-30140-0_49
intvolume: '      3221'
language:
- iso: eng
page: 544-555
place: Berlin, Heidelberg
publication: Proc. 12th Annual Symposium on Algorithms (ESA'04)
publication_identifier:
  isbn:
  - '9783540230250'
  - '9783540301400'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: Springer
status: public
title: Fast Multipoint Evaluation of Bivariate Polynomials
type: conference
user_id: '15415'
volume: 3221
year: '2004'
...
---
_id: '16474'
abstract:
- lang: eng
  text: "Given n distinct points p1, p2, ... , pn in the plane, the map labeling\r\nproblem
    with four squares is to place n axis-parallel equi-sized squares Q1, ... ,Qn\r\nof
    maximum possible size such that pi is a corner of Qi and no two squares overlap.\r\nThis
    problem is NP-hard and no algorithm with approximation ratio better\r\nthan 1/2
    exists unless P = NP [10].\r\nIn this paper, we consider a scenario where we want
    to visualize the information\r\ngathered by smart dust, i.e. by a large set of
    simple devices, each consisting of\r\na sensor and a sender that can gather sensor
    data and send it to a central station.\r\nOur task is to label (the positions
    of) these sensors in a way described by the\r\nlabeling problem above. Since these
    devices are not positioned accurately (for\r\nexample, they might be dropped from
    an airplane), this gives rise to consider the\r\nmap labeling problem under the
    assumption, that the positions of the points are\r\nnot fixed precisely, but perturbed
    by random noise. In other words, we consider\r\nthe smoothed complexity of the
    map labeling problem. We present an algorithm\r\nthat, under such an assumption
    and Gaussian random noise with sufficiently large\r\nvariance, has linear smoothed
    complexity."
author:
- first_name: Vikas
  full_name: Bansal, Vikas
  last_name: Bansal
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Christian
  full_name: Sohler, Christian
  last_name: Sohler
citation:
  ama: 'Bansal V, Meyer auf der Heide F, Sohler C. Labeling Smart Dust. In: <i>12th
    Annual European Symposium on Algorithms (ESA 2004)</i>. Vol 3221. Lecture Notes
    in Computer Science. Berlin, Heidelberg; 2004. doi:<a href="https://doi.org/10.1007/978-3-540-30140-0_9">10.1007/978-3-540-30140-0_9</a>'
  apa: Bansal, V., Meyer auf der Heide, F., &#38; Sohler, C. (2004). Labeling Smart
    Dust. In <i>12th Annual European Symposium on Algorithms (ESA 2004)</i> (Vol.
    3221). Berlin, Heidelberg. <a href="https://doi.org/10.1007/978-3-540-30140-0_9">https://doi.org/10.1007/978-3-540-30140-0_9</a>
  bibtex: '@inproceedings{Bansal_Meyer auf der Heide_Sohler_2004, place={Berlin, Heidelberg},
    series={Lecture Notes in Computer Science}, title={Labeling Smart Dust}, volume={3221},
    DOI={<a href="https://doi.org/10.1007/978-3-540-30140-0_9">10.1007/978-3-540-30140-0_9</a>},
    booktitle={12th Annual European Symposium on Algorithms (ESA 2004)}, author={Bansal,
    Vikas and Meyer auf der Heide, Friedhelm and Sohler, Christian}, year={2004},
    collection={Lecture Notes in Computer Science} }'
  chicago: Bansal, Vikas, Friedhelm Meyer auf der Heide, and Christian Sohler. “Labeling
    Smart Dust.” In <i>12th Annual European Symposium on Algorithms (ESA 2004)</i>,
    Vol. 3221. Lecture Notes in Computer Science. Berlin, Heidelberg, 2004. <a href="https://doi.org/10.1007/978-3-540-30140-0_9">https://doi.org/10.1007/978-3-540-30140-0_9</a>.
  ieee: V. Bansal, F. Meyer auf der Heide, and C. Sohler, “Labeling Smart Dust,” in
    <i>12th Annual European Symposium on Algorithms (ESA 2004)</i>, 2004, vol. 3221.
  mla: Bansal, Vikas, et al. “Labeling Smart Dust.” <i>12th Annual European Symposium
    on Algorithms (ESA 2004)</i>, vol. 3221, 2004, doi:<a href="https://doi.org/10.1007/978-3-540-30140-0_9">10.1007/978-3-540-30140-0_9</a>.
  short: 'V. Bansal, F. Meyer auf der Heide, C. Sohler, in: 12th Annual European Symposium
    on Algorithms (ESA 2004), Berlin, Heidelberg, 2004.'
date_created: 2020-04-08T11:07:57Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-540-30140-0_9
intvolume: '      3221'
language:
- iso: eng
place: Berlin, Heidelberg
publication: 12th Annual European Symposium on Algorithms (ESA 2004)
publication_identifier:
  isbn:
  - '9783540230250'
  - '9783540301400'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
series_title: Lecture Notes in Computer Science
status: public
title: Labeling Smart Dust
type: conference
user_id: '15415'
volume: 3221
year: '2004'
...