Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Physical Sciences and Mathematics
Algorithms For Covering Barrier Points By Mobile Sensors With Line Constraint, Princy Jain
Algorithms For Covering Barrier Points By Mobile Sensors With Line Constraint, Princy Jain
All Graduate Theses and Dissertations, Spring 1920 to Summer 2023
In this thesis, we develop efficient algorithms for the problem of covering barrier points by mobile sensors. Each sensor is represented by a point in the plane with the same covering range r so that any point within distance r from the sensor can be covered by the sensor. Given a set B of m points (called “barrier points”) and a set S of n points (representing the “sensors”) in the plane, the problem is to move the sensors so that each barrier point is covered by at least one sensor and the maximum movement of all sensors is minimized. …
Geometric Algorithms For Intervals And Related Problems, Shimin Li
Geometric Algorithms For Intervals And Related Problems, Shimin Li
All Graduate Theses and Dissertations, Spring 1920 to Summer 2023
In this dissertation, we study several problems related to intervals and develop efficient algorithms for them. Interval problems have many applications in reality because many objects, values, and ranges are intervals in nature, such as time intervals, distances, line segments, probabilities, etc. Problems on intervals are gaining attention also because intervals are among the most basic geometric objects, and for the same reason, computational geometry techniques find useful for attacking these problems. Specifically, the problems we study in this dissertation includes the following: balanced splitting on weighted intervals, minimizing the movements of spreading points, dispersing points on intervals, multiple barrier …
Geometric Facility Location Problems On Uncertain Data, Jingru Zhang
Geometric Facility Location Problems On Uncertain Data, Jingru Zhang
All Graduate Theses and Dissertations, Spring 1920 to Summer 2023
In this dissertation, we study several facility location problems on uncertain data. We mainly consider the k-center problem and many of its variations. These are classical problems in computer science and operations research. These problems on deterministic data have been studied extensively in the literature. We consider them on uncertain data because data in the real world is often associated with uncertainty due to measurement inaccuracy, sampling discrepancy, outdated data sources, resource limitation, etc. Although we focus on the theoretical study, the algorithms developed in this dissertation may find applications in other areas such as data clustering, wireless sensor …
A Computational Geometry Approach To Digital Image Contour Extraction, Pedro J. Tejada
A Computational Geometry Approach To Digital Image Contour Extraction, Pedro J. Tejada
All Graduate Theses and Dissertations, Spring 1920 to Summer 2023
We present a method for extracting contours from digital images, using techniques from computational geometry. Our approach is different from traditional pixel-based methods in image processing. Instead of working directly with pixels, we extract a set of oriented feature points from the input digital images, then apply classical geometric techniques, such as clustering, linking, and simplification, to find contours among these points. Experiments on synthetic and natural images show that our method can effectively extract contours, even from images with considerable noise; moreover, the extracted contours have a very compact representation.