Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-10893
Authors: Weitbrecht, Felix
Title: On the number of Delaunay Triangles occurring in all contiguous subsequenes
Issue Date: 2020
metadata.ubs.publikation.typ: Abschlussarbeit (Master)
metadata.ubs.publikation.seiten: 19
URI: http://elib.uni-stuttgart.de/handle/11682/10910
http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-109100
http://dx.doi.org/10.18419/opus-10893
Abstract: Given an ordered sequence of points P = {p1, p2, ..., pn}, we consider all contiguous subsequences Pi,j := {pi, ..., pj} of P and the set T of distinct Delaunay triangles within their Delaunay triangulations. For arbitrary point sets and orderings, we give an O(n^2) bound on |T|. Furthermore, for arbitrary point sets in uniformly random order, we give two proofs of a Θ(n log n) bound on E[|T|].
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
Masterarbeit.pdf226,91 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.