Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 13 of 13 for “"Sweep line"”.
-
Sweep-Line Extensions to the Multiple Object Intersection Problem: Methods and Applications in Graph Mining
… algorithmic paradigm, collectively known as the sweep-line or plane sweep algorithm. However, its application inherits a number of limitations including lack of versatility and lack of support for ad hoc intersection queries. With these limitations in mind, we design and implement a novel, exact, …
-
Efficient algorithms for answering geo-range query
… values, which takes O(n^3) running time. The Sweep-Line algorithm applies a conceptual line sweeping through the plane. The sweep-line moves through the plane and keeps tracking all the sensor points encountered. The algorithm takes O( n^2 \log n ) running time, while it still gives exact …
-
An investigation of the datagram congestion control protocol's connection management and synchronisation procedures
… retransmission. We therefore decided to use the sweepline method to verify both general and specific properties of the protocol, in an attempt to extend the results to more than one retransmission. In order to use the sweep-line method efficiently, we derive monotonic progress measures so that …
-
A Taxonomy of Polynomially Solvable Shop Problems with Limited Number of Machines or Jobs
… dynamic programming, greedy techniques and sweep line algorithms and the primary focus of this thesis is to give a taxonomy of such problems with their solutions. Additionally the thesis outlines a neighborhood search technique which uses the disjunctive graph model and which can be applied …
-
Effective Density Visualization of Multiple Overlapping Axis-Aligned Objects
… computational geometry methods based on the sweep line paradigm. These methods are fast and can determine the exact size of the overlap of multiple axis-aligned objects, therefore can effectively inform the visualization method. Towards that end, we propose OL-HeatMap, a novel density-based …
-
Accelerating Spatial Query Operations
… presenting algorithms using the GPU to perform line segment intersection for geometric operations. This paper presents two parallel algorithms implemented on the GPU that focus on the active list portion of the traditional serial plane sweep algorithm. The first algorithm uses a single block of …
-
Sensor Planning for Bayesian Nonparametric Target Modeling
… of the resultant approximation error decreasing linearly as the number of samples increases. Computational complexities for optimizing the novel information theoretic functions under sensor dynamics constraints are studied, and are proved to be NP-hard. A cumulative lower bound is then proposed …
-
Exact Generalized Voronoi Diagram Computation using a Sweepline Algorithm
… exact Generalized Voronoi Diagram from points, line segments and, connected lines including lines that connect to form simple polygons. Our technique is an extension of Fortune’s method. Our approach treats connected lines (or polygons) as a single site.
-
Efficient processing of Top-k queries on spatial and temporal data
… proposed approach by comparing it with a classic sweep line algorithm. We are the first to study the I/O efficient solution for depth-related problems which can be used for retrieving the top-k objects with linear scoring functions. Half-plane depth of a plane is the number of objects lying in the …
-
Computational methods for Quantitative Peptide Mass Spectrometry
… neue wissenschaftliche Beiträge. Der erste ist SweepWavelet, ein Algorithmus zur Quantifizierung von Peptiden aus LC-MS Daten. Die akkurate Quantifizierung von Peptiden und Proteinen ist ein wichtiges Thema in der biomedizinischen Forschung, da sie der erste Schritt in der rechnergestützten …
-
Qualitative topological coverage of unknown environments by mobile robots
… in implementation details, especially for online creation in unknown environments. It was later followed by Morse decomposition, which addressed issues on implementation such as planning with partial representation and cell boundary detection with range sensors. The work in this thesis was …
-
Qualitative Topological Coverage of Unknown Environments by Mobile Robots
… in implementation details, especially for online creation in unknown environments. It was later followed by Morse decomposition, which addressed issues on implementation such as planning with partial representation and cell boundary detection with range sensors. The work in this thesis was …