Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorIvor van der Hoog, Frank Staals
dc.contributor.authorEhrencron, T.M.
dc.date.accessioned2021-08-26T18:00:16Z
dc.date.available2021-08-26T18:00:16Z
dc.date.issued2021
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/41245
dc.description.abstractA well-studied class of geometrical problems is the class of point enclosing problems. Here we are given a point set P and a convex shape s. Either we have to enclose as many points of P with s or we have to enclose a certain number of points and we minimise the size of s. In both cases the input consists of a set points and value which is either the number of points k that we must enclose or the size r of the shape. We consider specifically the interval for 1-dimensional points and the circle and square for 2-dimensional points. Although these problems have been studied extensively in the last few decades, we take a different approach. Instead of solving one of these problems directly, we construct, for a specific problem, a data structure on the point set such that we can query either a value k or r (depending on the problem) and answer the problem more quickly. Building the data structure might take more time than computing the problem directly, but if we need to solve the same problem for different values of k or r, this approach can be faster than solving the problem from start for each individual input.
dc.description.sponsorshipUtrecht University
dc.format.extent808693
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.titleData Structures for Point Enclosing Problems on the Circle and the Square
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordscircle, circle enclosing, square, square enclosing
dc.subject.courseuuComputing Science


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record