---
_id: '17865'
abstract:
- lang: eng
text: We present a new output-sensitive rendering algorithm, the randomized z-buffer
algorithm. It renders an image of a three dimensional scene of triangular primitives
by reconstruction from a random sample of surface points which are chosen with
a probability proportional to the projected area of the objects. The approach
is independent of mesh connectivity and topology. It leads to a rendering time
that grows only logarithmically with the numbers of triangles in the scene and
to linear memory consumption, thus allowing walkthroughs of scenes of extreme
complexity. We consider different methods for image reconstruction which aim at
correctness, rendering speed and image quality and we develop an efficient data
structure for sample extraction in output-sensitive time which allows for efficient
dynamic updates of the scene. Experiments confirm that scenes consisting of some
hundred billion triangles can be rendered within seconds with an image quality
comparable to a conventional z-buffer rendering; in special cases, realtime performance
can be achieved.
author:
- first_name: Michael
full_name: Wand, Michael
last_name: Wand
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Wand M, Fischer M, Meyer auf der Heide F. Randomized Point Sampling for
Output-Sensitive Rendering of Complex Dynamic Scenes. Universität Paderborn;
2000.
apa: Wand, M., Fischer, M., & Meyer auf der Heide, F. (2000). Randomized
Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes. Universität
Paderborn.
bibtex: '@book{Wand_Fischer_Meyer auf der Heide_2000, place={Universität Paderborn},
title={Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic
Scenes}, author={Wand, Michael and Fischer, Matthias and Meyer auf der Heide,
Friedhelm}, year={2000} }'
chicago: Wand, Michael, Matthias Fischer, and Friedhelm Meyer auf der Heide. Randomized
Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes. Universität
Paderborn, 2000.
ieee: M. Wand, M. Fischer, and F. Meyer auf der Heide, Randomized Point Sampling
for Output-Sensitive Rendering of Complex Dynamic Scenes. Universität Paderborn,
2000.
mla: Wand, Michael, et al. Randomized Point Sampling for Output-Sensitive Rendering
of Complex Dynamic Scenes. 2000.
short: M. Wand, M. Fischer, F. Meyer auf der Heide, Randomized Point Sampling for
Output-Sensitive Rendering of Complex Dynamic Scenes, Universität Paderborn, 2000.
date_created: 2020-08-12T13:27:52Z
date_updated: 2022-01-06T06:53:21Z
ddc:
- '000'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-08-12T13:27:33Z
date_updated: 2020-08-12T13:27:33Z
file_id: '17866'
file_name: tr-ri-00-217.pdf
file_size: 921817
relation: main_file
success: 1
file_date_updated: 2020-08-12T13:27:33Z
has_accepted_license: '1'
language:
- iso: eng
place: Universität Paderborn
status: public
title: Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic
Scenes
type: report
user_id: '15415'
year: '2000'
...
---
_id: '18962'
author:
- first_name: Sathish
full_name: Govindarajan, Sathish
last_name: Govindarajan
- first_name: Tamas
full_name: Lukovszki, Tamas
last_name: Lukovszki
- first_name: Anil
full_name: Maheshwari, Anil
last_name: Maheshwari
- first_name: Norbert
full_name: Zeh, Norbert
last_name: Zeh
citation:
ama: 'Govindarajan S, Lukovszki T, Maheshwari A, Zeh N. I/O-Efficient Well-Separated
Pair Decomposition and Applications. In: Proceedings of the 8th Annual European
Symposium on Algorithms (ESA 2000), LNCS. ; 2000:585-614. doi:10.1007/s00453-005-1197-3'
apa: Govindarajan, S., Lukovszki, T., Maheshwari, A., & Zeh, N. (2000). I/O-Efficient
Well-Separated Pair Decomposition and Applications. In Proceedings of the 8th
Annual European Symposium on Algorithms (ESA 2000), LNCS (pp. 585–614). https://doi.org/10.1007/s00453-005-1197-3
bibtex: '@inproceedings{Govindarajan_Lukovszki_Maheshwari_Zeh_2000, title={I/O-Efficient
Well-Separated Pair Decomposition and Applications}, DOI={10.1007/s00453-005-1197-3},
booktitle={Proceedings of the 8th Annual European Symposium on Algorithms (ESA
2000), LNCS}, author={Govindarajan, Sathish and Lukovszki, Tamas and Maheshwari,
Anil and Zeh, Norbert}, year={2000}, pages={585–614} }'
chicago: Govindarajan, Sathish, Tamas Lukovszki, Anil Maheshwari, and Norbert Zeh.
“I/O-Efficient Well-Separated Pair Decomposition and Applications.” In Proceedings
of the 8th Annual European Symposium on Algorithms (ESA 2000), LNCS, 585–614,
2000. https://doi.org/10.1007/s00453-005-1197-3.
ieee: S. Govindarajan, T. Lukovszki, A. Maheshwari, and N. Zeh, “I/O-Efficient Well-Separated
Pair Decomposition and Applications,” in Proceedings of the 8th Annual European
Symposium on Algorithms (ESA 2000), LNCS, 2000, pp. 585–614.
mla: Govindarajan, Sathish, et al. “I/O-Efficient Well-Separated Pair Decomposition
and Applications.” Proceedings of the 8th Annual European Symposium on Algorithms
(ESA 2000), LNCS, 2000, pp. 585–614, doi:10.1007/s00453-005-1197-3.
short: 'S. Govindarajan, T. Lukovszki, A. Maheshwari, N. Zeh, in: Proceedings of
the 8th Annual European Symposium on Algorithms (ESA 2000), LNCS, 2000, pp. 585–614.'
date_created: 2020-09-03T13:21:02Z
date_updated: 2022-01-06T06:53:55Z
department:
- _id: '63'
doi: 10.1007/s00453-005-1197-3
language:
- iso: eng
page: 585-614
publication: Proceedings of the 8th Annual European Symposium on Algorithms (ESA 2000),
LNCS
publication_identifier:
issn:
- 0178-4617
- 1432-0541
publication_status: published
status: public
title: I/O-Efficient Well-Separated Pair Decomposition and Applications
type: conference
user_id: '15415'
year: '2000'
...
---
_id: '17990'
abstract:
- lang: eng
text: We consider the notion of Property Testing as applied to computational geometry.
We aim at developing efficient algorithms which determine whether a given (geometrical)
object has a predetermined property Q or is 'far' from any object having the property.
We show that many basic geometric properties have very efficient testing algorithms,
whose running time is significantly smaller than the object description size.
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Czumaj A, Sohler C, Ziegler M. Property Testing in Computational Geometry.
In: Proceedings of the 8th Annual European Symposium on Algorithms (ESA’00).
Vol 4698. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer; 2000:155-166.
doi:10.1007/3-540-45253-2_15'
apa: 'Czumaj, A., Sohler, C., & Ziegler, M. (2000). Property Testing in Computational
Geometry. In Proceedings of the 8th Annual European Symposium on Algorithms
(ESA’00) (Vol. 4698, pp. 155–166). Berlin, Heidelberg: Springer. https://doi.org/10.1007/3-540-45253-2_15'
bibtex: '@inproceedings{Czumaj_Sohler_Ziegler_2000, place={Berlin, Heidelberg},
series={Lecture Notes in Computer Science}, title={Property Testing in Computational
Geometry}, volume={4698}, DOI={10.1007/3-540-45253-2_15},
booktitle={Proceedings of the 8th Annual European Symposium on Algorithms (ESA’00)},
publisher={Springer}, author={Czumaj, Artur and Sohler, Christian and Ziegler,
Martin}, year={2000}, pages={155–166}, collection={Lecture Notes in Computer Science}
}'
chicago: 'Czumaj, Artur, Christian Sohler, and Martin Ziegler. “Property Testing
in Computational Geometry.” In Proceedings of the 8th Annual European Symposium
on Algorithms (ESA’00), 4698:155–66. Lecture Notes in Computer Science. Berlin,
Heidelberg: Springer, 2000. https://doi.org/10.1007/3-540-45253-2_15.'
ieee: A. Czumaj, C. Sohler, and M. Ziegler, “Property Testing in Computational Geometry,”
in Proceedings of the 8th Annual European Symposium on Algorithms (ESA’00),
2000, vol. 4698, pp. 155–166.
mla: Czumaj, Artur, et al. “Property Testing in Computational Geometry.” Proceedings
of the 8th Annual European Symposium on Algorithms (ESA’00), vol. 4698, Springer,
2000, pp. 155–66, doi:10.1007/3-540-45253-2_15.
short: 'A. Czumaj, C. Sohler, M. Ziegler, in: Proceedings of the 8th Annual European
Symposium on Algorithms (ESA’00), Springer, Berlin, Heidelberg, 2000, pp. 155–166.'
date_created: 2020-08-14T13:48:54Z
date_updated: 2022-01-06T06:53:24Z
department:
- _id: '63'
doi: 10.1007/3-540-45253-2_15
intvolume: ' 4698'
language:
- iso: eng
page: 155-166
place: Berlin, Heidelberg
publication: Proceedings of the 8th Annual European Symposium on Algorithms (ESA'00)
publication_identifier:
isbn:
- '9783540410041'
- '9783540452539'
issn:
- 0302-9743
publication_status: published
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Property Testing in Computational Geometry
type: conference
user_id: '15415'
volume: 4698
year: '2000'
...
---
_id: '18146'
abstract:
- lang: eng
text: 'Since its very beginning, linear algebra is a highly algorithmic subject.
Let us just mention the famous Gauss Algorithm which was invented before the theory
of algorithms has been developed. The purpose of this paper is to link linear
algebra explicitly to computable analysis, that is the theory of computable real
number functions. Especially, we will investigate in which sense the dimension
of a given linear subspace can be computed. The answer highly depends on how the
linear subspace is given: if it is given by a finite number of vectors whose linear
span represents the space, then the dimension does not depend continuously on
these vectors and consequently it cannot be computed. If the linear subspace is
represented via its distance function, which is a standard way to represent closed
subspaces in computable analysis, then the dimension does computably depend on
the distance function.'
author:
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
- first_name: Vasco
full_name: Brattka, Vasco
last_name: Brattka
citation:
ama: 'Ziegler M, Brattka V. Computing the Dimension of Linear Subspaces. In: SOFSEM
2000: Theory and Practice of Informatics. Vol 1963. Berlin, Heidelberg: Springer;
2000:450-458. doi:10.1007/3-540-44411-4_34'
apa: 'Ziegler, M., & Brattka, V. (2000). Computing the Dimension of Linear Subspaces.
In SOFSEM 2000: Theory and Practice of Informatics (Vol. 1963, pp. 450–458).
Berlin, Heidelberg: Springer. https://doi.org/10.1007/3-540-44411-4_34'
bibtex: '@inproceedings{Ziegler_Brattka_2000, place={Berlin, Heidelberg}, title={Computing
the Dimension of Linear Subspaces}, volume={1963}, DOI={10.1007/3-540-44411-4_34},
booktitle={SOFSEM 2000: Theory and Practice of Informatics}, publisher={Springer},
author={Ziegler, Martin and Brattka, Vasco}, year={2000}, pages={450–458} }'
chicago: 'Ziegler, Martin, and Vasco Brattka. “Computing the Dimension of Linear
Subspaces.” In SOFSEM 2000: Theory and Practice of Informatics, 1963:450–58.
Berlin, Heidelberg: Springer, 2000. https://doi.org/10.1007/3-540-44411-4_34.'
ieee: 'M. Ziegler and V. Brattka, “Computing the Dimension of Linear Subspaces,”
in SOFSEM 2000: Theory and Practice of Informatics, 2000, vol. 1963, pp.
450–458.'
mla: 'Ziegler, Martin, and Vasco Brattka. “Computing the Dimension of Linear Subspaces.”
SOFSEM 2000: Theory and Practice of Informatics, vol. 1963, Springer, 2000,
pp. 450–58, doi:10.1007/3-540-44411-4_34.'
short: 'M. Ziegler, V. Brattka, in: SOFSEM 2000: Theory and Practice of Informatics,
Springer, Berlin, Heidelberg, 2000, pp. 450–458.'
date_created: 2020-08-24T09:58:56Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
doi: 10.1007/3-540-44411-4_34
intvolume: ' 1963'
language:
- iso: eng
page: 450-458
place: Berlin, Heidelberg
publication: 'SOFSEM 2000: Theory and Practice of Informatics'
publication_identifier:
isbn:
- '9783540413486'
- '9783540444114'
issn:
- 0302-9743
publication_status: published
publisher: Springer
status: public
title: Computing the Dimension of Linear Subspaces
type: conference
user_id: '15415'
volume: 1963
year: '2000'
...
---
_id: '18150'
abstract:
- lang: eng
text: What is the minimum number of hyperplanes that slice all edges of the d-dimensional
hypercube? The answers have been known for d<=4.
This work settles the problem
for d=5 and d=6. More precisely, a computer search implies that 4 hyperplanes
do not suffice for this purpose (but 5 do).
We also develop computational approaches
for attacking this extremal problem from combinatorial geometry in higher dimensions.
They allow us to determine for example all maximal sliceable subsets of hypercube
edges up to dimension 7.
author:
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: 'Ziegler M, Sohler C. Computing Cut Numbers. In: Proceedings of the 12th
Canadian Conference on Computational Geometry (CCCG’00). ; 2000:73-79.'
apa: Ziegler, M., & Sohler, C. (2000). Computing Cut Numbers. In Proceedings
of the 12th Canadian Conference on Computational Geometry (CCCG’00) (pp. 73–79).
bibtex: '@inproceedings{Ziegler_Sohler_2000, title={Computing Cut Numbers}, booktitle={Proceedings
of the 12th Canadian Conference on Computational Geometry (CCCG’00)}, author={Ziegler,
Martin and Sohler, Christian}, year={2000}, pages={73–79} }'
chicago: Ziegler, Martin, and Christian Sohler. “Computing Cut Numbers.” In Proceedings
of the 12th Canadian Conference on Computational Geometry (CCCG’00), 73–79,
2000.
ieee: M. Ziegler and C. Sohler, “Computing Cut Numbers,” in Proceedings of the
12th Canadian Conference on Computational Geometry (CCCG’00), 2000, pp. 73–79.
mla: Ziegler, Martin, and Christian Sohler. “Computing Cut Numbers.” Proceedings
of the 12th Canadian Conference on Computational Geometry (CCCG’00), 2000,
pp. 73–79.
short: 'M. Ziegler, C. Sohler, in: Proceedings of the 12th Canadian Conference on
Computational Geometry (CCCG’00), 2000, pp. 73–79.'
date_created: 2020-08-24T10:10:40Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
language:
- iso: eng
page: 73-79
publication: Proceedings of the 12th Canadian Conference on Computational Geometry
(CCCG'00)
status: public
title: Computing Cut Numbers
type: conference
user_id: '15415'
year: '2000'
...
---
_id: '18446'
abstract:
- lang: eng
text: "We consider comparator networks M that are used repeatedly: while the output
produced by M is not sorted, it is fed again into M. Sorting algorithms working
in this way are called periodic. The number of parallel steps performed during
a single run of M is called its period, the sorting time of M is the total number
of parallel steps that are necessary to sort in the worst case. Periodic sorting
networks have the advantage that they need little hardware (control logic, wiring,
area) and that they are adaptive. We are interested in comparator networks of
a constant period, due to their potential applications in hardware design.\r\n\r\nPreviously,
very little was known on such networks. The fastest solutions required time O(nε)
where the depth was roughly 1/ε. We introduce a general method called periodification
scheme that converts automatically an arbitrary sorting network that sorts n items
in time T(n) and that has layout area A(n) into a sorting network that has period
5, sorts ***(n • T(n) items in time O(T(Journal of the ACM.
2000;45:944-967. doi:10.1145/355483.355490'
apa: 'Lorys, K., Wanka, R., Oesterdiekhoff, B., & Kutylowski, M. (2000). Periodification
Scheme: Constructing Sorting Networks with Constant Period. Journal of the
ACM, 45, 944–967. https://doi.org/10.1145/355483.355490'
bibtex: '@article{Lorys_Wanka_Oesterdiekhoff_Kutylowski_2000, title={Periodification
Scheme: Constructing Sorting Networks with Constant Period}, volume={45}, DOI={10.1145/355483.355490}, journal={Journal
of the ACM}, author={Lorys, Krzysztof and Wanka, Rolf and Oesterdiekhoff, Brigitte
and Kutylowski, Miroslaw}, year={2000}, pages={944–967} }'
chicago: 'Lorys, Krzysztof, Rolf Wanka, Brigitte Oesterdiekhoff, and Miroslaw Kutylowski.
“Periodification Scheme: Constructing Sorting Networks with Constant Period.”
Journal of the ACM 45 (2000): 944–67. https://doi.org/10.1145/355483.355490.'
ieee: 'K. Lorys, R. Wanka, B. Oesterdiekhoff, and M. Kutylowski, “Periodification
Scheme: Constructing Sorting Networks with Constant Period,” Journal of the
ACM, vol. 45, pp. 944–967, 2000, doi: 10.1145/355483.355490.'
mla: 'Lorys, Krzysztof, et al. “Periodification Scheme: Constructing Sorting Networks
with Constant Period.” Journal of the ACM, vol. 45, 2000, pp. 944–67, doi:10.1145/355483.355490.'
short: K. Lorys, R. Wanka, B. Oesterdiekhoff, M. Kutylowski, Journal of the ACM
45 (2000) 944–967.
date_created: 2020-08-27T11:49:50Z
date_updated: 2022-01-06T06:53:32Z
department:
- _id: '63'
doi: 10.1145/355483.355490
intvolume: ' 45'
language:
- iso: eng
page: 944-967
publication: Journal of the ACM
status: public
title: 'Periodification Scheme: Constructing Sorting Networks with Constant Period'
type: journal_article
user_id: '15415'
volume: 45
year: '2000'
...
---
_id: '2211'
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Czumaj A, Scheideler C. A New Algorithmic Approach to the General Lovász Local
Lemma with Applications to Scheduling and Satisfiability Problems . In: 32nd
ACM Symposium on Theory of Computing. ; 2000:38-47.'
apa: Czumaj, A., & Scheideler, C. (2000). A New Algorithmic Approach to the
General Lovász Local Lemma with Applications to Scheduling and Satisfiability
Problems . In 32nd ACM Symposium on Theory of Computing (pp. 38–47).
bibtex: '@inproceedings{Czumaj_Scheideler_2000, title={A New Algorithmic Approach
to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability
Problems }, booktitle={32nd ACM Symposium on Theory of Computing}, author={Czumaj,
Artur and Scheideler, Christian}, year={2000}, pages={38–47} }'
chicago: Czumaj, Artur, and Christian Scheideler. “A New Algorithmic Approach to
the General Lovász Local Lemma with Applications to Scheduling and Satisfiability
Problems .” In 32nd ACM Symposium on Theory of Computing, 38–47, 2000.
ieee: A. Czumaj and C. Scheideler, “A New Algorithmic Approach to the General Lovász
Local Lemma with Applications to Scheduling and Satisfiability Problems ,” in
32nd ACM Symposium on Theory of Computing, 2000, pp. 38–47.
mla: Czumaj, Artur, and Christian Scheideler. “A New Algorithmic Approach to the
General Lovász Local Lemma with Applications to Scheduling and Satisfiability
Problems .” 32nd ACM Symposium on Theory of Computing, 2000, pp. 38–47.
short: 'A. Czumaj, C. Scheideler, in: 32nd ACM Symposium on Theory of Computing,
2000, pp. 38–47.'
date_created: 2018-04-05T07:02:46Z
date_updated: 2022-01-06T06:55:26Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2018-04-12T08:37:23Z
date_updated: 2018-04-12T08:37:23Z
file_id: '2296'
file_name: STOC-00.pdf
file_size: 190083
relation: main_file
file_date_updated: 2018-04-12T08:37:23Z
has_accepted_license: '1'
language:
- iso: eng
oa: '1'
page: 38-47
publication: 32nd ACM Symposium on Theory of Computing
status: public
title: 'A New Algorithmic Approach to the General Lovász Local Lemma with Applications
to Scheduling and Satisfiability Problems '
type: conference
urn: '22111'
user_id: '14955'
year: '2000'
...
---
_id: '16495'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Matthias
full_name: Westermann, Matthias
last_name: Westermann
citation:
ama: 'Meyer auf der Heide F, Räcke H, Westermann M. Data management in hierarchical
bus networks. In: Proceedings of the Twelfth Annual ACM Symposium on Parallel
Algorithms and Architectures - SPAA ’00. ; 2000. doi:10.1145/341800.341814'
apa: Meyer auf der Heide, F., Räcke, H., & Westermann, M. (2000). Data management
in hierarchical bus networks. Proceedings of the Twelfth Annual ACM Symposium
on Parallel Algorithms and Architectures - SPAA ’00. https://doi.org/10.1145/341800.341814
bibtex: '@inproceedings{Meyer auf der Heide_Räcke_Westermann_2000, title={Data management
in hierarchical bus networks}, DOI={10.1145/341800.341814},
booktitle={Proceedings of the twelfth annual ACM symposium on Parallel algorithms
and architectures - SPAA ’00}, author={Meyer auf der Heide, Friedhelm and Räcke,
Harald and Westermann, Matthias}, year={2000} }'
chicago: Meyer auf der Heide, Friedhelm, Harald Räcke, and Matthias Westermann.
“Data Management in Hierarchical Bus Networks.” In Proceedings of the Twelfth
Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA ’00,
2000. https://doi.org/10.1145/341800.341814.
ieee: 'F. Meyer auf der Heide, H. Räcke, and M. Westermann, “Data management in
hierarchical bus networks,” 2000, doi: 10.1145/341800.341814.'
mla: Meyer auf der Heide, Friedhelm, et al. “Data Management in Hierarchical Bus
Networks.” Proceedings of the Twelfth Annual ACM Symposium on Parallel Algorithms
and Architectures - SPAA ’00, 2000, doi:10.1145/341800.341814.
short: 'F. Meyer auf der Heide, H. Räcke, M. Westermann, in: Proceedings of the
Twelfth Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA
’00, 2000.'
date_created: 2020-04-09T13:06:23Z
date_updated: 2022-01-06T06:52:51Z
department:
- _id: '63'
doi: 10.1145/341800.341814
language:
- iso: eng
publication: Proceedings of the twelfth annual ACM symposium on Parallel algorithms
and architectures - SPAA '00
publication_identifier:
isbn:
- '1581131852'
publication_status: published
status: public
title: Data management in hierarchical bus networks
type: conference
user_id: '15415'
year: '2000'
...
---
_id: '16496'
abstract:
- lang: eng
text: We present a general framework for the development of on-line algorithms for
data management in networks with limited memory capacities. These algorithms dynamically
create and delete copies of shared data objects that can be read and written by
the nodes in the network. Our algorithms aim to minimize the congestion, i.e.,
the maximum communication load over all network resources, so that that none of
these resources become a communication bottleneck. We give several examples of
networks for which our framework yields efficient algorithms, including meshes,
fat-trees, hypercubic networks, and complete networks. For example, our framework
yields an $O(d cdot log n)$-competitive caching algorithm for $d$-dimensional
meshes of size $n$ with respect to the congestion on the communication links,
and an $O(1)$-competitive algorithms for complete networks with respect to the
congestion at the memory modules due to remote accesses. Previous work on data
management in networks either neglects memory capacity constraints or minimizes
only the total communication load, i.e., the sum of the communication load over
all resources, which may produce congestion as some of the links become bottlenecks.
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Berthold
full_name: Vöcking, Berthold
last_name: Vöcking
- first_name: Matthias
full_name: Westermann, Matthias
last_name: Westermann
citation:
ama: 'Meyer auf der Heide F, Vöcking B, Westermann M. Caching in networks. In: SODA
’00: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms.
; 2000:430–439.'
apa: 'Meyer auf der Heide, F., Vöcking, B., & Westermann, M. (2000). Caching
in networks. In SODA ’00: Proceedings of the eleventh annual ACM-SIAM symposium
on Discrete algorithms (pp. 430–439).'
bibtex: '@inproceedings{Meyer auf der Heide_Vöcking_Westermann_2000, title={Caching
in networks}, booktitle={SODA ’00: Proceedings of the eleventh annual ACM-SIAM
symposium on Discrete algorithms}, author={Meyer auf der Heide, Friedhelm and
Vöcking, Berthold and Westermann, Matthias}, year={2000}, pages={430–439} }'
chicago: 'Meyer auf der Heide, Friedhelm, Berthold Vöcking, and Matthias Westermann.
“Caching in Networks.” In SODA ’00: Proceedings of the Eleventh Annual ACM-SIAM
Symposium on Discrete Algorithms, 430–439, 2000.'
ieee: 'F. Meyer auf der Heide, B. Vöcking, and M. Westermann, “Caching in networks,”
in SODA ’00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete
algorithms, 2000, pp. 430–439.'
mla: 'Meyer auf der Heide, Friedhelm, et al. “Caching in Networks.” SODA ’00:
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms,
2000, pp. 430–439.'
short: 'F. Meyer auf der Heide, B. Vöcking, M. Westermann, in: SODA ’00: Proceedings
of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 430–439.'
date_created: 2020-04-09T13:16:15Z
date_updated: 2022-01-06T06:52:51Z
department:
- _id: '63'
language:
- iso: eng
page: 430–439
publication: 'SODA ''00: Proceedings of the eleventh annual ACM-SIAM symposium on
Discrete algorithms'
publication_identifier:
isbn:
- '0898714532'
status: public
title: Caching in networks
type: conference
user_id: '15415'
year: '2000'
...
---
_id: '16497'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Mirosław
full_name: Kutyłowski, Mirosław
last_name: Kutyłowski
- first_name: Prabhakar
full_name: Ragde, Prabhakar
last_name: Ragde
citation:
ama: 'Meyer auf der Heide F, Kutyłowski M, Ragde P. Complexity Theory and Algorithms.
In: Euro-Par 2000 Parallel Processing. Berlin, Heidelberg; 2000. doi:10.1007/3-540-44520-x_59'
apa: Meyer auf der Heide, F., Kutyłowski, M., & Ragde, P. (2000). Complexity
Theory and Algorithms. In Euro-Par 2000 Parallel Processing. Berlin, Heidelberg.
https://doi.org/10.1007/3-540-44520-x_59
bibtex: '@inbook{Meyer auf der Heide_Kutyłowski_Ragde_2000, place={Berlin, Heidelberg},
title={Complexity Theory and Algorithms}, DOI={10.1007/3-540-44520-x_59},
booktitle={Euro-Par 2000 Parallel Processing}, author={Meyer auf der Heide, Friedhelm
and Kutyłowski, Mirosław and Ragde, Prabhakar}, year={2000} }'
chicago: Meyer auf der Heide, Friedhelm, Mirosław Kutyłowski, and Prabhakar Ragde.
“Complexity Theory and Algorithms.” In Euro-Par 2000 Parallel Processing.
Berlin, Heidelberg, 2000. https://doi.org/10.1007/3-540-44520-x_59.
ieee: F. Meyer auf der Heide, M. Kutyłowski, and P. Ragde, “Complexity Theory and
Algorithms,” in Euro-Par 2000 Parallel Processing, Berlin, Heidelberg,
2000.
mla: Meyer auf der Heide, Friedhelm, et al. “Complexity Theory and Algorithms.”
Euro-Par 2000 Parallel Processing, 2000, doi:10.1007/3-540-44520-x_59.
short: 'F. Meyer auf der Heide, M. Kutyłowski, P. Ragde, in: Euro-Par 2000 Parallel
Processing, Berlin, Heidelberg, 2000.'
date_created: 2020-04-09T13:30:45Z
date_updated: 2022-01-06T06:52:51Z
department:
- _id: '63'
doi: 10.1007/3-540-44520-x_59
language:
- iso: eng
place: Berlin, Heidelberg
publication: Euro-Par 2000 Parallel Processing
publication_identifier:
isbn:
- '9783540679561'
- '9783540445203'
issn:
- 0302-9743
publication_status: published
status: public
title: Complexity Theory and Algorithms
type: book_chapter
user_id: '15415'
year: '2000'
...
---
_id: '17010'
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Volker
full_name: Stemann, Volker
last_name: Stemann
citation:
ama: Czumaj A, Meyer auf der Heide F, Stemann V. Contention Resolution in Hashing
Based Shared Memory Simulations. SIAM Journal on Computing. 2000:1703-1739.
doi:10.1137/s009753979529564x
apa: Czumaj, A., Meyer auf der Heide, F., & Stemann, V. (2000). Contention Resolution
in Hashing Based Shared Memory Simulations. SIAM Journal on Computing,
1703–1739. https://doi.org/10.1137/s009753979529564x
bibtex: '@article{Czumaj_Meyer auf der Heide_Stemann_2000, title={Contention Resolution
in Hashing Based Shared Memory Simulations}, DOI={10.1137/s009753979529564x},
journal={SIAM Journal on Computing}, author={Czumaj, Artur and Meyer auf der Heide,
Friedhelm and Stemann, Volker}, year={2000}, pages={1703–1739} }'
chicago: Czumaj, Artur, Friedhelm Meyer auf der Heide, and Volker Stemann. “Contention
Resolution in Hashing Based Shared Memory Simulations.” SIAM Journal on Computing,
2000, 1703–39. https://doi.org/10.1137/s009753979529564x.
ieee: A. Czumaj, F. Meyer auf der Heide, and V. Stemann, “Contention Resolution
in Hashing Based Shared Memory Simulations,” SIAM Journal on Computing,
pp. 1703–1739, 2000.
mla: Czumaj, Artur, et al. “Contention Resolution in Hashing Based Shared Memory
Simulations.” SIAM Journal on Computing, 2000, pp. 1703–39, doi:10.1137/s009753979529564x.
short: A. Czumaj, F. Meyer auf der Heide, V. Stemann, SIAM Journal on Computing
(2000) 1703–1739.
date_created: 2020-05-18T13:47:36Z
date_updated: 2022-01-06T06:53:01Z
department:
- _id: '63'
doi: 10.1137/s009753979529564x
language:
- iso: eng
page: 1703-1739
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: Contention Resolution in Hashing Based Shared Memory Simulations
type: journal_article
user_id: '15415'
year: '2000'
...
---
_id: '16345'
article_type: original
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Rolf
full_name: Wanka, Rolf
last_name: Wanka
citation:
ama: Meyer auf der Heide F, Wanka R. Von der Hollerith-Maschine zum Parallelrechner
- Die alltägliche Aufgabe des Sortierens als Fortschrittsmotor für die Informatik.
ForschungsForum Paderborn. 2000:112-116.
apa: Meyer auf der Heide, F., & Wanka, R. (2000). Von der Hollerith-Maschine
zum Parallelrechner - Die alltägliche Aufgabe des Sortierens als Fortschrittsmotor
für die Informatik. ForschungsForum Paderborn, 112–116.
bibtex: '@article{Meyer auf der Heide_Wanka_2000, title={Von der Hollerith-Maschine
zum Parallelrechner - Die alltägliche Aufgabe des Sortierens als Fortschrittsmotor
für die Informatik}, journal={ForschungsForum Paderborn}, author={Meyer auf der
Heide, Friedhelm and Wanka, Rolf}, year={2000}, pages={112–116} }'
chicago: Meyer auf der Heide, Friedhelm, and Rolf Wanka. “Von Der Hollerith-Maschine
Zum Parallelrechner - Die Alltägliche Aufgabe Des Sortierens Als Fortschrittsmotor
Für Die Informatik.” ForschungsForum Paderborn, 2000, 112–16.
ieee: F. Meyer auf der Heide and R. Wanka, “Von der Hollerith-Maschine zum Parallelrechner
- Die alltägliche Aufgabe des Sortierens als Fortschrittsmotor für die Informatik,”
ForschungsForum Paderborn, pp. 112–116, 2000.
mla: Meyer auf der Heide, Friedhelm, and Rolf Wanka. “Von Der Hollerith-Maschine
Zum Parallelrechner - Die Alltägliche Aufgabe Des Sortierens Als Fortschrittsmotor
Für Die Informatik.” ForschungsForum Paderborn, 2000, pp. 112–16.
short: F. Meyer auf der Heide, R. Wanka, ForschungsForum Paderborn (2000) 112–116.
date_created: 2020-03-24T10:59:27Z
date_updated: 2022-01-06T06:52:49Z
ddc:
- '000'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-08-04T13:17:46Z
date_updated: 2020-08-04T13:17:46Z
file_id: '17588'
file_name: FFP-06-2000.pdf
file_size: 477845
relation: main_file
success: 1
file_date_updated: 2020-08-04T13:17:46Z
has_accepted_license: '1'
language:
- iso: eng
page: 112-116
publication: ForschungsForum Paderborn
publication_identifier:
unknown:
- ISBN 978-3-942647-99-1
status: public
title: Von der Hollerith-Maschine zum Parallelrechner - Die alltägliche Aufgabe des
Sortierens als Fortschrittsmotor für die Informatik
type: journal_article
user_id: '15415'
year: '2000'
...
---
_id: '19784'
author:
- first_name: Christian
full_name: Scheideler, Christian
last_name: Scheideler
citation:
ama: Scheideler C. Probabilistic Methods for Coordination Problems.; 2000.
apa: Scheideler, C. (2000). Probabilistic Methods for Coordination Problems.
bibtex: '@book{Scheideler_2000, title={Probabilistic Methods for Coordination Problems},
author={Scheideler, Christian}, year={2000} }'
chicago: Scheideler, Christian. Probabilistic Methods for Coordination Problems,
2000.
ieee: C. Scheideler, Probabilistic Methods for Coordination Problems. 2000.
mla: Scheideler, Christian. Probabilistic Methods for Coordination Problems.
2000.
short: C. Scheideler, Probabilistic Methods for Coordination Problems, 2000.
date_created: 2020-09-30T10:05:34Z
date_updated: 2024-07-12T07:00:50Z
department:
- _id: '63'
- _id: '26'
language:
- iso: eng
publication_identifier:
isbn:
- 3-931466-77-9
status: public
title: Probabilistic Methods for Coordination Problems
type: habilitation
user_id: '1112'
year: '2000'
...
---
_id: '19732'
abstract:
- lang: eng
text: The Paderborn University BSP (PUB) library is a parallel C library based on
the BSP model. The basic library supports buffered and unbuffered asynchronous
communication between any pair of processors, and a mechanism for synchronizing
the processors in a barrier style. In ad-dition, it provides routines for collective
communication on arbitrary subsets of processors, partition operations, and a
zero-cost synchronization mechanism. Furthermore, some techniques used in its
implementation deviate significantly from the techniques used in other BSP libraries.
author:
- first_name: Olaf
full_name: Bonorden, Olaf
last_name: Bonorden
- first_name: Bernhardus
full_name: Juurlink, Bernhardus
last_name: Juurlink
- first_name: I.
full_name: Von Otte, I.
last_name: Von Otte
- first_name: Ingo
full_name: Rieping, Ingo
last_name: Rieping
citation:
ama: 'Bonorden O, Juurlink B, Von Otte I, Rieping I. The Paderborn university BSP
(PUB) library-design, implementation and performance. In: Proceedings 13th
International Parallel Processing Symposium and 10th Symposium on Parallel and
Distributed Processing. ; 1999:99-104. doi:10.1109/ipps.1999.760442'
apa: Bonorden, O., Juurlink, B., Von Otte, I., & Rieping, I. (1999). The Paderborn
university BSP (PUB) library-design, implementation and performance. Proceedings
13th International Parallel Processing Symposium and 10th Symposium on Parallel
and Distributed Processing, 99–104. https://doi.org/10.1109/ipps.1999.760442
bibtex: '@inproceedings{Bonorden_Juurlink_Von Otte_Rieping_1999, title={The Paderborn
university BSP (PUB) library-design, implementation and performance}, DOI={10.1109/ipps.1999.760442},
booktitle={Proceedings 13th International Parallel Processing Symposium and 10th
Symposium on Parallel and Distributed Processing}, author={Bonorden, Olaf and
Juurlink, Bernhardus and Von Otte, I. and Rieping, Ingo}, year={1999}, pages={99–104}
}'
chicago: Bonorden, Olaf, Bernhardus Juurlink, I. Von Otte, and Ingo Rieping. “The
Paderborn University BSP (PUB) Library-Design, Implementation and Performance.”
In Proceedings 13th International Parallel Processing Symposium and 10th Symposium
on Parallel and Distributed Processing, 99–104, 1999. https://doi.org/10.1109/ipps.1999.760442.
ieee: 'O. Bonorden, B. Juurlink, I. Von Otte, and I. Rieping, “The Paderborn university
BSP (PUB) library-design, implementation and performance,” in Proceedings 13th
International Parallel Processing Symposium and 10th Symposium on Parallel and
Distributed Processing, 1999, pp. 99–104, doi: 10.1109/ipps.1999.760442.'
mla: Bonorden, Olaf, et al. “The Paderborn University BSP (PUB) Library-Design,
Implementation and Performance.” Proceedings 13th International Parallel Processing
Symposium and 10th Symposium on Parallel and Distributed Processing, 1999,
pp. 99–104, doi:10.1109/ipps.1999.760442.
short: 'O. Bonorden, B. Juurlink, I. Von Otte, I. Rieping, in: Proceedings 13th
International Parallel Processing Symposium and 10th Symposium on Parallel and
Distributed Processing, 1999, pp. 99–104.'
date_created: 2020-09-28T12:11:30Z
date_updated: 2022-01-06T06:54:10Z
department:
- _id: '63'
doi: 10.1109/ipps.1999.760442
language:
- iso: eng
page: 99-104
publication: Proceedings 13th International Parallel Processing Symposium and 10th
Symposium on Parallel and Distributed Processing
publication_identifier:
isbn:
- '0769501435'
publication_status: published
status: public
title: The Paderborn university BSP (PUB) library-design, implementation and performance
type: conference
user_id: '15415'
year: '1999'
...
---
_id: '2151'
author:
- first_name: Michele
full_name: Flammini, Michele
last_name: Flammini
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: Flammini M, Scheideler C. Simple, Efficient Routing Schemes for All-Optical
Networks. Theory Comput Syst. 1999;32(3):387--420. doi:10.1007/s002240000123
apa: Flammini, M., & Scheideler, C. (1999). Simple, Efficient Routing Schemes
for All-Optical Networks. Theory Comput. Syst., 32(3), 387--420.
https://doi.org/10.1007/s002240000123
bibtex: '@article{Flammini_Scheideler_1999, title={Simple, Efficient Routing Schemes
for All-Optical Networks}, volume={32}, DOI={10.1007/s002240000123},
number={3}, journal={Theory Comput. Syst.}, author={Flammini, Michele and Scheideler,
Christian}, year={1999}, pages={387--420} }'
chicago: 'Flammini, Michele, and Christian Scheideler. “Simple, Efficient Routing
Schemes for All-Optical Networks.” Theory Comput. Syst. 32, no. 3 (1999):
387--420. https://doi.org/10.1007/s002240000123.'
ieee: M. Flammini and C. Scheideler, “Simple, Efficient Routing Schemes for All-Optical
Networks,” Theory Comput. Syst., vol. 32, no. 3, pp. 387--420, 1999.
mla: Flammini, Michele, and Christian Scheideler. “Simple, Efficient Routing Schemes
for All-Optical Networks.” Theory Comput. Syst., vol. 32, no. 3, 1999,
pp. 387--420, doi:10.1007/s002240000123.
short: M. Flammini, C. Scheideler, Theory Comput. Syst. 32 (1999) 387--420.
date_created: 2018-04-03T06:22:14Z
date_updated: 2022-01-06T06:55:02Z
department:
- _id: '79'
- _id: '63'
doi: 10.1007/s002240000123
intvolume: ' 32'
issue: '3'
language:
- iso: eng
page: 387--420
publication: Theory Comput. Syst.
status: public
title: Simple, Efficient Routing Schemes for All-Optical Networks
type: journal_article
user_id: '14955'
volume: 32
year: '1999'
...
---
_id: '2164'
author:
- first_name: Petra
full_name: Berenbrink, Petra
last_name: Berenbrink
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Berenbrink P, Scheideler C. Locally Efficient On-Line Strategies for Routing
Packets Along Fixed Paths. In: SODA. ; 1999:112--121.'
apa: Berenbrink, P., & Scheideler, C. (1999). Locally Efficient On-Line Strategies
for Routing Packets Along Fixed Paths. In SODA (pp. 112--121).
bibtex: '@inproceedings{Berenbrink_Scheideler_1999, title={Locally Efficient On-Line
Strategies for Routing Packets Along Fixed Paths}, booktitle={SODA}, author={Berenbrink,
Petra and Scheideler, Christian}, year={1999}, pages={112--121} }'
chicago: Berenbrink, Petra, and Christian Scheideler. “Locally Efficient On-Line
Strategies for Routing Packets Along Fixed Paths.” In SODA, 112--121, 1999.
ieee: P. Berenbrink and C. Scheideler, “Locally Efficient On-Line Strategies for
Routing Packets Along Fixed Paths,” in SODA, 1999, pp. 112--121.
mla: Berenbrink, Petra, and Christian Scheideler. “Locally Efficient On-Line Strategies
for Routing Packets Along Fixed Paths.” SODA, 1999, pp. 112--121.
short: 'P. Berenbrink, C. Scheideler, in: SODA, 1999, pp. 112--121.'
date_created: 2018-04-03T08:56:06Z
date_updated: 2022-01-06T06:55:09Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2018-04-12T07:34:50Z
date_updated: 2018-04-12T07:34:50Z
file_id: '2288'
file_name: SODA-99.pdf
file_size: 179058
relation: main_file
file_date_updated: 2018-04-12T07:34:50Z
has_accepted_license: '1'
language:
- iso: eng
oa: '1'
page: 112--121
publication: SODA
status: public
title: Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths
type: conference
urn: '21649'
user_id: '14955'
year: '1999'
...
---
_id: '2165'
author:
- first_name: Petra
full_name: Berenbrink, Petra
last_name: Berenbrink
- first_name: Marco
full_name: Riedel, Marco
last_name: Riedel
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Berenbrink P, Riedel M, Scheideler C. Simple Competitive Request Scheduling
Strategies. In: SPAA. ; 1999:33--42.'
apa: Berenbrink, P., Riedel, M., & Scheideler, C. (1999). Simple Competitive
Request Scheduling Strategies. In SPAA (pp. 33--42).
bibtex: '@inproceedings{Berenbrink_Riedel_Scheideler_1999, title={Simple Competitive
Request Scheduling Strategies}, booktitle={SPAA}, author={Berenbrink, Petra and
Riedel, Marco and Scheideler, Christian}, year={1999}, pages={33--42} }'
chicago: Berenbrink, Petra, Marco Riedel, and Christian Scheideler. “Simple Competitive
Request Scheduling Strategies.” In SPAA, 33--42, 1999.
ieee: P. Berenbrink, M. Riedel, and C. Scheideler, “Simple Competitive Request Scheduling
Strategies,” in SPAA, 1999, pp. 33--42.
mla: Berenbrink, Petra, et al. “Simple Competitive Request Scheduling Strategies.”
SPAA, 1999, pp. 33--42.
short: 'P. Berenbrink, M. Riedel, C. Scheideler, in: SPAA, 1999, pp. 33--42.'
date_created: 2018-04-03T08:56:45Z
date_updated: 2022-01-06T06:55:09Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2018-04-12T07:36:27Z
date_updated: 2018-04-12T07:36:27Z
file_id: '2290'
file_name: SPAA-99.pdf
file_size: 144422
relation: main_file
file_date_updated: 2018-04-12T07:36:27Z
has_accepted_license: '1'
language:
- iso: eng
oa: '1'
page: 33--42
publication: SPAA
status: public
title: Simple Competitive Request Scheduling Strategies
type: conference
urn: '21658'
user_id: '14955'
year: '1999'
...
---
_id: '17864'
abstract:
- lang: eng
text: "A geometric spanner with vertex set P in Rd is a sparse approximation of
the complete Euclidean graph determined by P. We introduce the notion of partitioned
neighborhood graphs (PNGs), unifying and generalizing most constructions of spanners
treated in literature. Two important parameters characterizing their properties
are the outdegree k in N and the stretch factor f>1 describing the \x93quality\x94
of approximation. PNGs have been throughly investigated with respect to small
values of f. We present in this work results about small values of k. The aim
of minimizing k rather than f arises from two observations:\r\n\r\n* k determines
the amount of space required for storing PNGs.\r\n\r\n* Many algorithms employing
a (previously constructed) spanner have running times depending on its outdegree.\r\n\r\nOur
results include, for fixed dimensions d as well as asymptotically, upper and lower
bounds on this optimal value of k. The upper bounds are shown constructively and
yield efficient algorithms for actually computing the corresponding PNGs even
in degenerate cases.\r\n"
author:
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Tamas
full_name: Lukovszki, Tamas
last_name: Lukovszki
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Fischer M, Lukovszki T, Ziegler M. Partitioned neighborhood spanners of minimal
outdegree. In: Proceedings of the 11th Canadian Conference on Computational
Geometry. Vancouver; 1999.'
apa: Fischer, M., Lukovszki, T., & Ziegler, M. (1999). Partitioned neighborhood
spanners of minimal outdegree. In Proceedings of the 11th Canadian Conference
on Computational Geometry. Vancouver.
bibtex: '@inproceedings{Fischer_Lukovszki_Ziegler_1999, place={Vancouver}, title={Partitioned
neighborhood spanners of minimal outdegree}, booktitle={Proceedings of the 11th
Canadian Conference on Computational Geometry}, author={Fischer, Matthias and
Lukovszki, Tamas and Ziegler, Martin}, year={1999} }'
chicago: Fischer, Matthias, Tamas Lukovszki, and Martin Ziegler. “Partitioned Neighborhood
Spanners of Minimal Outdegree.” In Proceedings of the 11th Canadian Conference
on Computational Geometry. Vancouver, 1999.
ieee: M. Fischer, T. Lukovszki, and M. Ziegler, “Partitioned neighborhood spanners
of minimal outdegree,” in Proceedings of the 11th Canadian Conference on Computational
Geometry, 1999.
mla: Fischer, Matthias, et al. “Partitioned Neighborhood Spanners of Minimal Outdegree.”
Proceedings of the 11th Canadian Conference on Computational Geometry,
1999.
short: 'M. Fischer, T. Lukovszki, M. Ziegler, in: Proceedings of the 11th Canadian
Conference on Computational Geometry, Vancouver, 1999.'
date_created: 2020-08-12T13:12:00Z
date_updated: 2022-01-06T06:53:21Z
ddc:
- '000'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-08-27T11:14:43Z
date_updated: 2020-08-27T11:14:43Z
file_id: '18438'
file_name: hni-id-729.pdf
file_size: 209419
relation: main_file
success: 1
file_date_updated: 2020-08-27T11:14:43Z
has_accepted_license: '1'
language:
- iso: eng
place: Vancouver
publication: Proceedings of the 11th Canadian Conference on Computational Geometry
related_material:
link:
- relation: confirmation
url: http://www.cccg.ca/proceedings/1999/fp36.pdf
status: public
title: Partitioned neighborhood spanners of minimal outdegree
type: conference
user_id: '15415'
year: '1999'
...
---
_id: '18747'
abstract:
- lang: eng
text: We present a new ( O(n) ) algorithm to compute good orders for the point set
of a Delaunay triangulation of ( n ) points in the plane. Such a good order makes
reconstruction in ( O(n) ) time with a simple algorithm possible. In contrast
to the algorithm of Snoeyink and van Kreveld cite1, which is based on independent
sets, our algorithm uses a breadth first search (BFS) to obtain these orders.
Both approaches construct such orders by repeatedly removing a constant fraction
of vertices from the current triangulation. The advantage of the BFS approach
is that we can give significantly better bounds on the fraction of removed points
in a phase of the algorithm. We can prove that a single phase of our algorithm
removes at least ( frac13 ) of the points, even if we restrict the degree of the
points (at the time they are removed) to 6. We implemented and compared both algorithms.
Our algorithms is slightly faster and achieves about 15% better vertex data compression
when using a simple variable length code to encode the differences between two
consecutive vertices of the given order.
author:
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: 'Sohler C. Fast Reconstruction of Delaunay Triangulations. In: Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99). ; 1999:136-141.'
apa: Sohler, C. (1999). Fast Reconstruction of Delaunay Triangulations. In Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99) (pp.
136–141).
bibtex: '@inproceedings{Sohler_1999, title={Fast Reconstruction of Delaunay Triangulations},
booktitle={Proceedings of the 11th Canadian Conference on Computational Geometry
( CCCG’99)}, author={Sohler, Christian}, year={1999}, pages={136–141} }'
chicago: Sohler, Christian. “Fast Reconstruction of Delaunay Triangulations.” In
Proceedings of the 11th Canadian Conference on Computational Geometry ( CCCG’99),
136–41, 1999.
ieee: C. Sohler, “Fast Reconstruction of Delaunay Triangulations,” in Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99), 1999,
pp. 136–141.
mla: Sohler, Christian. “Fast Reconstruction of Delaunay Triangulations.” Proceedings
of the 11th Canadian Conference on Computational Geometry ( CCCG’99), 1999,
pp. 136–41.
short: 'C. Sohler, in: Proceedings of the 11th Canadian Conference on Computational
Geometry ( CCCG’99), 1999, pp. 136–141.'
date_created: 2020-09-01T10:43:10Z
date_updated: 2022-01-06T06:53:51Z
department:
- _id: '63'
language:
- iso: eng
page: 136-141
publication: Proceedings of the 11th Canadian Conference on Computational Geometry
( CCCG'99)
status: public
title: Fast Reconstruction of Delaunay Triangulations
type: conference
user_id: '15415'
year: '1999'
...
---
_id: '18942'
author:
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
citation:
ama: Lukovszki T. New Results on Geometric Spanners and Their Applications.
Vol 63. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 1999.
apa: Lukovszki, T. (1999). New Results on Geometric Spanners and Their Applications
(Vol. 63). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.
bibtex: '@book{Lukovszki_1999, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}, title={New Results on Geometric Spanners and Their Applications},
volume={63}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn},
author={Lukovszki, Tamás}, year={1999}, collection={Verlagsschriftenreihe des
Heinz Nixdorf Instituts, Paderborn} }'
chicago: Lukovszki, Tamás. New Results on Geometric Spanners and Their Applications.
Vol. 63. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 1999.
ieee: T. Lukovszki, New Results on Geometric Spanners and Their Applications,
vol. 63. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 1999.
mla: Lukovszki, Tamás. New Results on Geometric Spanners and Their Applications.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 1999.
short: T. Lukovszki, New Results on Geometric Spanners and Their Applications, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 1999.
date_created: 2020-09-03T11:41:51Z
date_updated: 2022-01-06T06:53:55Z
ddc:
- '000'
department:
- _id: '63'
- _id: '26'
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-09-22T13:12:09Z
date_updated: 2020-09-22T13:12:09Z
file_id: '19641'
file_name: pub-hni-495.pdf
file_size: 1077329
relation: main_file
success: 1
file_date_updated: 2020-09-22T13:12:09Z
has_accepted_license: '1'
intvolume: ' 63'
language:
- iso: eng
publication_identifier:
isbn:
- '3-931466-62-0 '
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: New Results on Geometric Spanners and Their Applications
type: dissertation
user_id: '5786'
volume: 63
year: '1999'
...