Physical Sciences and Mathematics Commons^™

Exact Generalized Voronoi Diagram Computation Using A Sweepline Algorithm, Daniel Marsden

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Voronoi Diagrams can provide useful spatial information. Little work has been done on computing exact Voronoi Diagrams when the sites are more complex than a point. We introduce a technique that measures the 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.

Research On Multi-Objective Optimization Method Based On Model, Jianjun Liu, Guangya Si, Yanzheng Wang, Dachuan He

Journal of System Simulation

Abstract: There is a model-based algorithm for the optimization of multiple objective functions by means of black-box evaluation is proposed. The algorithm iteratively generates candidate solutions from a mixture distribution over the solution space and updates the mixture distribution based on the sampled solutions’ domination count, such that the future search is biased towards the set of Pareto optimal solutions. The proposed algorithm seeks to find a mixture distribution on the solution space so that each component of the mixture distribution is a degenerate distribution centered at a Pareto optimal solution and each estimated Pareto optimal solution is uniformly spread …

Qwasi: The Quantum Walk Simulator, Warren V. Wilson

Theses and Dissertations

As quantum computing continues to evolve, the ability to design and analyze novel quantum algorithms becomes a necessary focus for research. In many instances, the virtues of quantum algorithms only become evident when compared to their classical counterparts, so a study of the former often begins with a consideration of the latter. This is very much the case with quantum walk algorithms, as the success of random walks and their many, varied applications have inspired much interest in quantum correlates. Unfortunately, finding purely algebraic solutions for quantum walks is an elusive endeavor. At best, and when solvable, they require simple …

Design Of Unified Algorithm For Sampling Mpdu, Ti Zhou, Miao Yi, Yang Jian

Journal of System Simulation

Abstract: The standard of CCSDS AOS is used in space exploration because of the process of the standard airspace system. The spacecraft missions have used multi-protocol data unit (MPDU) to multiplex the package channels. The range of MPDU and the data are different in different spacecrafts. This process brings some problems in the maintenance and the correctness of the algorithms of virtual channel multiplexing in simulation system. The applications of CCSDS in the world were researched, and the general definitions of MPDU in these missions were described. A circle memory was given to buffer the data of MPDU, two general …

Study Of Parallelized Graph Clustering Algorithm Based On Spark, Dongjiang Liu, Jianhui Li

Journal of System Simulation

Abstract: The parallelized graph clustering algorithm is researched. A new parallelized graph clustering algorithm is proposed based on Spark. As the top operation of Spark occupies a lot of memory space, a new algorithm which is used to substitute the top operation is proposed to reduce the memory consumption. By improving bottom up hierarchical clustering algorithm, the speed of the proposed algorithm is improved. A new data filtering method based on the feature of graph data is proposed. By the method, the running time and memory space comsuption is reduced greatly. The reason of the high efficiency of this filtering …

Telemetry Parameters Simulation Of Spacecraft Based On Computation Tree, Ti Zhou, Miao Yi

Journal of System Simulation

Abstract: Simulation system of spacecrafts' Telemetry and Command (TT&C) needs to simulate lots of telemetry parameters in every missions, whose computing algorithms are different. In the past applications, these algorithms are fixed as codes in software programs, so it is very difficult to improve the maintainability and reuse of the simulation system. By studying the computing methods of telemetry parameters described in configuration files, a design scheme was given in which the algorithms of parameters were flexibly configured, and the principle of methods were described specially in computing parameters, software models, data structure and algorithms. In this framework, the algorithms …

Towards Distributed Node Similarity Search On Graphs, Tianming Zhang, Yunjun Gao, Baihua Zheng, Lu Chen, Shiting Wen, Wei Guo

Research Collection School Of Computing and Information Systems

Node similarity search on graphs has wide applications in recommendation, link prediction, to name just a few. However, existing studies are insufficient due to two reasons: (i) the scale of the real-world graph is growing rapidly, and (ii) vertices are always associated with complex attributes. In this paper, we propose an efficiently distributed framework to support node similarity search on massive graphs, which considers both graph structure correlation and node attribute similarity in metric spaces. The framework consists of preprocessing stage and query stage. In the preprocessing stage, a parallel KD-tree construction (KDC) algorithm is developed to form a newly …

A Parallel Algorithm And Implementation To Compute Spatial Autocorrelation (Hotspot) Using Matlab, Mingjun Li

Master's Theses (2009 -)

Being a spatial autocorrelation visualization tool in recent years, hotspot is often used in various fields, such as disease analysis, crime analysis, and weather conditions analysis and prediction in a certain area. Most of the research in hot spot analysis is in applying the concept to a variety of fields and to gain insights on the statistical significance prevalent in the clustering of data. Only a few of them discussed the efficiency and optimization of the algorithm. Commonly, these kinds of analyses would be based upon a huge dataset about space and time, and the conventional algorithm would take too …

Approximation And Computational Complexity Of Some Hammock Variations Of The Poset Cover Problem, Ivy Ordanel, Proceso L. Fernandez Jr, Richelle Ann B. Juayong, Henry N. Adorna

Department of Information Systems & Computer Science Faculty Publications

The Hammock(⏟𝟐, 𝟐 , … , 𝟐 / 𝒌 )-Poset Cover Problem is a variation of the Poset Cover Problem with the same input – set {𝑳_𝟏, 𝑳_𝟐, … , 𝑳_𝒎} of linear orders over the set {𝟏, 𝟐, … ,𝒏}, but the solution is restricted to a set of simple hammock(𝟐⏟, 𝟐 , … , 𝟐 / 𝒌 ) posets. The problem is NP-Hard when 𝒌 ≥ 𝟑 but is in 𝑷 when 𝒌 = 𝟏. The computational complexity of the problem when 𝒌 = 𝟐 is not yet known. In this paper, …

Designing Fractal Line Pied-De-Poules: A Case Study In Algorithmic Design Mediating Between Culture And Fractal Mathematics, Loe M.G. Feijs

Journal of Humanistic Mathematics

Millions of people own and wear pied-de-poule (houndstooth) garments. The pattern has an intriguing basic figure and a typical set of symmetries. The origin of the pattern lies in a specific type of weaving. In this article I apply computational techniques to modernize this ancient decorative pattern. In particular I describe a way to enrich pied-de-poule with a fractal structure.

Although a first fractal line pied-de-poule was shown at Bridges 2015, a number of fundamental questions still remained. The following questions are addressed in this article: Does the original pied-de-poule appear as a limit case when the fractal structure is …

Searching For Needles In The Cosmic Haystack, Thomas Ryan Devine

Graduate Theses, Dissertations, and Problem Reports

Searching for pulsar signals in radio astronomy data sets is a difficult task. The data sets are extremely large, approaching the petabyte scale, and are growing larger as instruments become more advanced. Big Data brings with it big challenges. Processing the data to identify candidate pulsar signals is computationally expensive and must utilize parallelism to be scalable. Labeling benchmarks for supervised classification is costly. To compound the problem, pulsar signals are very rare, e.g., only 0.05% of the instances in one data set represent pulsars. Furthermore, there are many different approaches to candidate classification with no consensus on a best …