View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Data Structures for Point Enclosing Problems on the Circle and the Square

        Thumbnail
        View/Open
        thesis.pdf (789.7Kb)
        Publication date
        2021
        Author
        Ehrencron, T.M.
        Metadata
        Show full item record
        Summary
        A 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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/41245
        Collections
        • Theses
        Utrecht university logo