Due to advancement in next-generation sequencing (NGS) technology, ultra-large datasets have been generated for further studies. These datasets contain a large amount of erroneous data. It is a computational problem to detect and correct the errors to improve performance of future applications, e.g., de novo assembly. In this article, we present a MapReduce-based algorithm, CloudEC, to correct sequencing errors in NGS data. We use five datasets and GAGE benchmark to compare efficiency and efficacy of CloudEC with CloudRS and error correction module of ALLPATHS-LG. Experiments show that CloudEC is 1.6 times faster than CloudRS. The corrected reads are then assembled by Velvet assembler, and the assembled results are examined by GAGE benchmark for correctness of assembly. It is shown that the correct N50 of the assembled contigs with CloudEC as the error corrector is larger than that with CloudRS as the error corrector, and is comparable to that with ALLPATHS-LG as the error corrector.

We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G=(V,E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an f-approximation for this problem, improving over a previous result of (2f+2)(1+epsilon) by Cheung et al to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions.

Biochips that are made of Micro Electro Mechanical Systems (MEMS) are concerned by everyone in recent years. The advantages of biochips are high accuracy and fast reaction rate with only a small volume consumption of samples and reagents. Among various types of biochips, flow-based microfluidic biochips receive much attention recently, especially the programmable microfluidic device (PMD). PMDs are capable of performing multitude functions in one platform without requiring any hardware modifications. As the size of chips increase, flow routing becomes more complicated. Traditional method to manually control multiple flows is inefficient and it may not have feasible assay completion time. Fortunately, PMDs has high potential to route flows with pure software programs to overcome the drawbacks of traditional methods. However, naive software program that simply minimizing assay completion time may cause flow-congestion problems and unexpected mixing between different assays, i,e., fluidic constraint. To conduct a viable experiment, a feasible program should not only minimize assay completion time but also consider congestion problems and fluidic constraint. Therefore, we formulate the flow routing problem and propose a routability-driven flow routing algorithm which considers the fluidic constraint and minimizes the assay completion time on PMDs.

A hash algorithm converts data into compact strings. In the multimedia domain, effective hashing is the key to large-scale similarity search in high-dimensional feature space. A limit of existing hashing techniques is that they typically use single features. In order to improve search performance, it is necessary to utilize multiple features. Due to the compactness requirement, concatenation of hash values from different features is not an optimal solution. Thus a fusion process is desired. In this paper, we solve the multiple feature fusion problem by a hash bit selection framework. Given multiple features, we derive an n-bit hash value of improved performance compared with hash values of the same length computed from each individual feature. The framework utilizes a feature-independent hash algorithm to generate a sufficient number of bits from each feature, and selects n bits from the hash bit pool by leveraging pair-wise label information. The metric bit reliability is used for ranking the bits. It is estimated by bit-level hypothesis testing. In addition, we also take into account the dependence among bits. A weighted graph is constructed for refined bit selection, where the bit reliability is used as vertex weights and the mutual information among hash bits is used as edge weights. We demonstrate our framework with LSH. Extensive experiments confirm that our method is effective, and outperforms several state-of-the-art methods.

We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V, E) with a maximum edge size f. Each edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an O(f) bi-approximation for VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of k geq 2, a cover with a cost ratio of (1+ frac{1}{k - 1})(f - 1) to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of f^2 via augmenting the available multiplicity by a factor of f.

In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and then the follower opens the second. Each customer will patronize the facility closest to him (ties broken in favor of the leader's one), thereby decides the market share of the two players. The goal is to find the best position for the leader’s facility so that his market share is maximized. The best algorithm for this problem is an O(n^2 log n)-time parametric search approach, which searches over the space of possible market share values. In the same paper, Drezner also proposed a general version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower's facility is not allowed to be located within a distance R from the leader's. He proposed an O(n^5 log n)-time algorithm for this general version by identifying O(n^4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n^4) candidate points, and present an O(n^2 log n)-time algorithm for the general version, thereby closing the O(n^3) gap between the two bounds.

Next-generation sequencing (NGS) data are a rapidly growing example of big data and a source of new knowledge in science. However, sequencing errors remain unavoidable and reduce the quality of NGS data. Error correction, therefore, is a critical step in the successful utilization of NGS data, including de novo genome assembly and DNA resequencing. Since NGS throughput doubles approximately every five months and the length of NGS records (i.e., reads) is increasing, improvements in efficiency and effectiveness of computational strategies are needed. In this study, we aim to improve the performance of CloudRS, an open-source MapReduce application designed to correct sequencing errors in NGS data. We introduce the readmessage (RM) diagram to represent the set of messages, i.e., the key-value pairs generated on each read. We also present the Gradient-number Votes (GNV) scheme in order to trim off portions of the RM diagram, thereby reducing the total size of messages associated with each read. Experimental results show that the GNV scheme successfully reduce execution time and improve the quality of the de novo genome assembly.

Rapid growth in capacity makes flow-based microfluidic biochips a promising candidate for biochemical analysis because they can integrate more complex functions. However, as the number of components grows, the total length of flow channels between components must increase exponentially. Recent empirical studies show that long flow channels are vulnerable due to blocking and leakage defects. Thus, it is desirable to minimize the total length of flow channels for robustness. Also, for timing-sensitive biochemical assays, increase in the longest length of flow channel will delay the assay completion time and lead to variation of fluid, thereby affecting the correctness of outcome. The increasing number of components, including the pre-placed components, on the chip makes the flow channel routing problem even more complicated. In this paper, we propose an efficient obstacle-avoiding rectilinear Steiner minimum tree algorithm to deal with flow channel routing problem in flow-based microfluidic biochips. Based on the concept of Kruskal algorithm and formulating the considerations as a bi-criteria function, our algorithm is capable of simultaneously minimizing the total length and the longest length of flow channel.

Detecting complex video events based on audio and visual modalities is still a largely unresolved issue. While the conventional video representation methods extract each modality ineffectively, we propose a regularized multi-modality deep learning for video event detection. We first build an auto-encoder based on unconstrained minimization and adopt the conjugate gradient method with linear search for optimization. The learned auto-encoder can capture the relationship between the audio and visual modality corresponding to the same video event at each layer of the network. To make the network robust to local variance, we adopt the commonly used local contrast normalization and spatial maximum pooling to each modality for video representation. Compared with traditional methods using manually designed features, our method is more efficient. Experimental results on publicly available video event detection datasets demonstrate that the proposed method consistently outperforms the state-of-the-art video representation methods.

We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59. Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm.

Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and without intersecting any obstacle. To deal with multiple routing layers and preferred routing orientations, we consider the multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theoretically different from the 2D one, and propose a reduction to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results.

Next-generation sequencing (NGS) technologies produce huge amounts of data. These sequencing data unavoidably are accompanied by the occurrence of sequencing errors which constitutes one of the major problems of further analyses. Error correction is indeed one of the critical steps to the success of NGS applications such as de novo genome assembly and DNA resequencing as illustrated in literature. However, it requires computing time and memory space heavily. To design an algorithm to improve data quality by efficiently utilizing on-demand computing resources in the cloud is a challenge for biologists and computer scientists. In this study, we present an error-correction algorithm, called the CloudRS algorithm, for correcting errors in NGS data. The CloudRS algorithm aims at emulating the notion of error correction algorithm of ALLPATHS-LG on the Hadoop/ MapReduce framework. It is conservative in correcting sequencing errors to avoid introducing false decisions, e.g., when dealing with reads from repetitive regions. We also illustrate several probabilistic measures we introduce into CloudRS to make the algorithm more efficient without sacrificing its effectiveness. Running time of using up to 80 instances each with 8 computing units shows satisfactory speedup. Experiments of comparing with other error correction programs show that CloudRS algorithm performs lower false positive rate for most evaluation benchmarks and higher sensitivity on genome S. cerevisiae. We demonstrate that CloudRS algorithm provides significant improvements in the quality of the resulting contigs on benchmarks of NGS de novo assembly.

The MapReduce framework has become the de facto choice for big data analysis in a variety of applications. In MapReduce programming model, computation is distributed to a cluster of computing nodes that runs in parallel. The performance of a MapReduce application is thus affected by system and middleware, characteristics of data, and design and implementation of the algorithms. In this study, we focus on performance optimization of a MapReduce application, i.e., CloudRS, which tackles on the problem of detecting and removing errors in the next-generation sequencing de novo genomic data. We present three strategies, i.e., contentexchange, content-grouping, and index-only strategies, of communication between the Map() and Reduce() functions. The three strategies differ in the way messages are exchanged between the two functions. We also present experimental results to compare performance of the three strategies.

We investigate the higher-order Voronoi diagrams of n point sites with respect to the geodesic distance in a simple polygon with h > 0 polygonal holes and c corners. Given a set of n point sites, the kth-order Voronoi diagram partitions the plane into several regions such that all points in a region share the same k nearest sites. The nearest-site (first-order) geodesic Voronoi diagram has already been well-studied, and its total complexity is O(n+c). On the other hand, Bae and Chwa [3] recently proved that the total complexity of the farthest-site ((n − 1)st-order) geodesic Voronoi diagram and the number of faces in the diagram are Θ(nc) and Θ(nh), respectively. It is of high interest to know what happens between the first-order and the (n − 1)st-order geodesic Voronoi diagrams. In this paper we prove that the total complexity of the kth-order geodesic Voronoi diagram is Θ(k(n − k) + kc), and the number of faces in the diagram is Θ(k(n − k) + kh). Our results successfully explain the variation from the nearest-site to the farthest-site geodesic Voronoi diagrams, i.e., from k = 1 to k = n − 1, and also illustrate the formation of a disconnected Voronoi region, which does not occur in many commonly used distance metrics, such as the Euclidean, L1, and city metrics. We show that the kth-order geodesic Voronoi diagram can be computed in O(k2(n+c) log(n+c)) time using an iterative algorithm.

Visual domain adaptation addresses the problem of adapting the sample distribution of the source domain to the target domain, where the recognition task is intended but the data distributions are different. In this paper, we present a low-rank reconstruction method to reduce the domain distribution disparity. Specifically, we transform the visual samples in the source domain into an intermediate representation such that each transformed source sample can be linearly reconstructed by the samples of the target domain. Unlike the existing work, our method captures the intrinsic relatedness of the source samples during the adaptation process while uncovering the noises and outliers in the source domain that cannot be adapted, making it more robust than previous methods. We formulate our problem as a constrained nuclear norm and ℓ2, 1norm minimization objective and then adopt the Augmented Lagrange Multiplier (ALM) method for the optimization. Extensive experiments on various visual adaptation tasks show that the proposed method consistently and significantly beats the state-of-the-art domain adaptation methods.

We consider the multi-layer obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem and propose a reduction to transform a multi-layer instance into a 3D instance. Based on the reduction we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results.

Joint audio-visual patterns often exist in videos and provide strong multi-modal cues for detecting multimedia events. However, conventional methods generally fuse the visual and audio information only at a superficial level, without adequately exploring deep intrinsic joint patterns. In this paper, we propose a joint audio-visual bi-modal representation, called bi-modal words. We first build a bipartite graph to model relation across the quantized words extracted from the visual and audio modalities. Partitioning over the bipartite graph is then applied to construct the bi-modal words that reveal the joint patterns across modalities. Finally, different pooling strategies are employed to re-quantize the visual and audio words into the bi-modal words and form bi-modal Bag-of-Words representations that are fed to subsequent multimedia event classifiers. We experimentally show that the proposed multi-modal feature achieves statistically significant performance gains over methods using individual visual and audio features alone and alternative multi-modal fusion methods. Moreover, we found that average pooling is the most suitable strategy for bi-modal feature generation.

For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, we present a Steiner-point-based algorithm that achieves the best practical performance among existing heuristics. We first propose a new concept of Steiner point locations, creating a linear-space routing graph with satisfactory Steiner point candidates to resolve the bottleneck of most existing heuristics. Then, we propose a Steiner-point-based framework to yield a solution, which is close to the key to the handling of the OARSMT problem. Experimental results show that this algorithm achieves excellent solution quality and speed performance at the same time. We also extend the Steiner-point-based framework to the obstacle-avoiding preferred direction Steiner tree problem with a good performance.

In multiple-Instance Learning (MIL), training class labels are attached to sets of bags composed of unlabeled instances, and the goal is to deal with classification of bags. Most previous MIL algorithms, which tackle classification problems, consider each instance as a represented feature. Although the algorithms work well in some prediction problems, considering diverse features to represent an instance may provide more significant information for learning task. Moreover, since each instance may be mapped into diverse feature spaces, encountering a large number of irrelevant or redundant features is inevitable. In this paper, we propose a method to select relevant instances and concurrently consider multiple features for each instance, which is termed as MIL-MFS. MIL-MFS is based on multiple kernel learning (MKL), and it iteratively selects the fusing multiple features for classifier training. Experimental results show that the MIL-MFS combined with multiple kernel learning can significantly improve the classification performance.

Scene images typically include diverse and distinctive properties. It is reasonable to consider different features in establishing a scene category recognition system with a promising performance. We propose an adaptive model to represent various features in a unified domain, i.e., a set of kernels, and transform the discriminant information contained in each kernel into a set of weak learners, called dyadic hyper cuts. Based on this model, we present a novel approach to carrying out incremental multiple kernel learning for feature fusion by applying AdaBoost to the union of the sets of weak learners. We further evaluate the performance of this approach by a benchmark dataset for scene category recognition. Experimental results show a significantly improved performance in both accuracy and efficiency.

The k-means clustering algorithm is a widely used scheme to solve the clustering problem which classifies a given set of n data points in m-dimensional space into k clusters, whose centers are obtained by the centroids of the points in the same cluster. The problem with privacy consideration has been studied, when the data is distributed among different parties and the privacy of the distributed data is to be preserved. In this paper, we apply the concept of parallel computing to solve the privacy-preserving multi-party k-means clustering problem, when the data is vertically partitioned and horizontally partitioned respectively among different parties. We present algorithms for solving the problems for these two data partition models that run in O(nk) time and in O(m(k + log(n=k))) time respectively. The time complexities of the algorithms are much better than others without parallel computing.

Re-ranking the returned images from a query relies on two important steps to improve its effectiveness: the estimation of the image relevance and the enhancement of the similarity function. However, attaining an effective visual similarity and an accurate re-ranking are quite challenging. We address these issues by first evaluating the image relevance to the query from the dataset according to the visual features and the co-occurrence of local patches of images. Then we boost the visual similarity measure associated with image relevance, and propose an enhancement algorithm, called Boosting-MKL, which not only incrementally learns the feature fusion but also generally preserves the initial local ranking. Specifically, we perform a random walk over a similarity graph for re-ranking. The experimental results demonstrate that our proposed approach significantly improves the effectiveness of visual similarity measure and the performance of image reranking.

MOTIVATION: Homologous genomic sequences between species usually contain different rearrangement events. Whether some specific patterns existed in the breakpoint regions that caused such events to occur is still unclear. To resolve this question, it is necessary to determine the location of breakpoints at the nucleotide level. The availability of sequences near breakpoints would further facilitate the related studies. We thus need a tool that can identify breakpoints and align the neighboring sequences. Although local alignment tools can detect rearrangement events, they only report a set of discontinuous alignments, where the detailed alignments in the breakpoint regions are usually missing. Global alignment tools are even less appropriate for these tasks since most of them are designed to align the conserved regions between sequences in a consistent order, i.e. they do not consider rearrangement events. RESULTS: We propose an effective and efficient pairwise sequence alignment algorithm, called GR-Aligner (Genomic Rearrangement Aligner), which can find breakpoints of rearrangement events by integrating the forward and reverse alignments of the breakpoint regions flanked by homologously rearranged sequences. In addition, GR-Aligner also provides an option to view the alignments of sequences extended to the breakpoints. These outputs provide materials for studying possible evolutionary mechanisms and biological functionalities of the rearrangement.

Algorithm visualization is a unique research topic that integrates engineering skills such as computer graphics, system programming, database management, computer networks, etc., to facilitate algorithmic researchers in testing their ideas, demonstrating new findings, and teaching algorithm design in the classroom. Within the broad applications of algorithm visualization, there still remain performance issues that deserve further research, e.g., system portability, collaboration capability, and animation effect in 3D environments. Using modern technologies of Java programming, we develop an algorithm visualization and debugging system, dubbed GeoBuilder, for geometric computing. The GeoBuilder system features Java's promising portability, engagement of collaboration in algorithm development, and automatic camera positioning for tracking 3D geometric objects. In this paper, we describe the design of the GeoBuilder system and demonstrate its applications.

In this paper, we present a design method for a discrete-time iterative learning control system by using output recurrent fuzzy neural network (ORFNN). Two ORFNNs are employed to design the control structure. One is used as an identifier called output recurrent fuzzy neural identifier (ORFNI) and the other used as a controller called output recurrent fuzzy neural controller (ORFNC). The ORFNI for identification of the unknown plant is introduced to provide the plant sensitivity which is then applied to the design of ORFNC. All the weights of ORFNI and ORFNC will be tuned during the control iteration and identification process respectively in order to achieve a desired learning performance. The adaptive laws for the weights of ORFNI and ORFNC and the analysis of learning performances are determined via a Lyapunov like analysis. It is shown that the identification error will asymptotically converge to zero and output tracking error will asymptotically converge to a residual set which depends on the initial resetting error.

This paper proposes a new fuzzy neural network based reinforcement adaptive iterative learning controller for a class of nonlinear systems. Different from some existing reinforcement learning schemes, the reinforcement adaptive iterative learning controller has the advantages of rigorous proofs without using an approximation of the plant Jacobian. The critic is appended into the reinforcement adaptive iterative learning controller to generate the reinforcement signal, which provides a degree of satisfaction about the tracking performance. In addition, the reinforcement signal can be further applied in the weight adaptation rules. Iterative learning components of the reinforcement adaptive iterative learning controller are designed to compensate for the uncertainties of plant nonlinearities. The overall adaptive scheme guarantees all adjustable parameters and the internal signals remain bounded for all iterations. Moreover, the norm of tracking error vector at each time instant will asymptotically converge to a tunable residual set as iteration goes to infinity even the initial state error exists. Finally, a simulation result is given to demonstrate the learning performance of the fuzzy neural network based reinforcement adaptive iterative learning controller.

BACKGROUND: The significant advances in microarray and proteomics analyses have resulted in an exponential increase in potential new targets and have promised to shed light on the identification of disease markers and cellular pathways. We aim to collect and decipher the HCC-related genes at the systems level. RESULTS: Here, we build an integrative platform, the Encyclopedia of Hepatocellular Carcinoma genes Online, dubbed EHCO http://ehco.iis.sinica.edu.tw, to systematically collect, organize and compare the pileup of unsorted HCC-related studies by using natural language processing and softbots. Among the eight gene set collections, ranging across PubMed, SAGE, microarray, and proteomics data, there are 2,906 genes in total; however, more than 77% genes are only included once, suggesting that tremendous efforts need to be exerted to characterize the relationship between HCC and these genes. Of these HCC inventories, protein binding represents the largest proportion (~25%) from Gene Ontology analysis. In fact, many differentially expressed gene sets in EHCO could form interaction networks (e.g. HBV-associated HCC network) by using available human protein-protein interaction datasets. To further highlight the potential new targets in the inferred network from EHCO, we combine comparative genomics and interactomics approaches to analyze 120 evolutionary conserved and overexpressed genes in HCC. 47 out of 120 queries can form a highly interactive network with 18 queries serving as hubs. CONCLUSION: This architectural map may represent the first step toward the attempt to decipher the hepatocarcinogenesis at the systems level. Targeting hubs and/or disruption of the network formation might reveal novel strategy for HCC treatment.

BACKGROUND: When aligning several hundreds or thousands of sequences, such as epidemic virus sequences or homologous/orthologous sequences of some big gene families, to reconstruct the epidemiological history or their phylogenies, how to analyze and visualize the alignment results of many sequences has become a new challenge for computational biologists. Although there are several tools available for visualization of very long sequence alignments, few of them are applicable to the alignments of many sequences. RESULTS: A multiple-logo alignment visualization tool, called Phylo-mLogo, is presented in this paper. Phylo-mLogo calculates the variabilities and homogeneities of alignment sequences by base frequencies or entropies. Different from the traditional representations of sequence logos, Phylo-mLogo not only displays the global logo patterns of the whole alignment of multiple sequences, but also demonstrates their local homologous logos for each clade hierarchically. In addition, Phylo-mLogo also allows the user to focus only on the analysis of some important, structurally or functionally constrained sites in the alignment selected by the user or by built-in automatic calculation. CONCLUSION: With Phylo-mLogo, the user can symbolically and hierarchically visualize hundreds of aligned sequences simultaneously and easily check the changes of their amino acid sites when analyzing many homologous/orthologous or influenza virus sequences. More information of Phylo-mLogo can be found at URL http://biocomp.iis.sinica.edu.tw/phylomlogo.

Geometric algorithm visualization techniques are very important to algorithmic research in geometric computing. The relevant applications include geometric algorithm development, testing, demonstration and teaching. Within these topics, there still remain performance issues to improve system portability, animation effect and so on. In this paper, we present a geometric algorithm visualization system that is featured by Java's portability and the "dynamic decision of camera position" for 3D geometric algorithm visualization.

Benchmark tests are often used to evaluate the quality of products by a set of common criteria. In this paper we describe a computational problem solving environment based on open source codes and an algorithm benchmark system, which is embedded in the environment as a plug-in system. The algorithm benchmark system can be used to compare the performance of various algorithms or to evaluate the behavior of an algorithm with different input instances. The current implementation allows users to compare or evaluate algorithms written in C/C++. Some examples of the algorithm benchmark system that evaluates the memory utilization, time complexity and the output of algorithms are also presented. Algorithm benchmark impresses the learning effect; students can not only comprehend the performance of respective algorithms but also write their own programs to challenge the best known results.

BACKGROUND: Deluged by the rate and complexity of completed genomic sequences, the need to align longer sequences becomes more urgent, and many more tools have thus been developed. In the initial stage of genomic sequence analysis, a biologist is usually faced with the questions of how to choose the best tool to align sequences of interest and how to analyze and visualize the alignment results, and then with the question of whether poorly aligned regions produced by the tool are indeed not homologous or are just results due to inappropriate alignment tools or scoring systems used. Although several systematic evaluations of multiple sequence alignment (MSA) programs have been proposed, they may not provide a standard-bearer for most biologists because those poorly aligned regions in these evaluations are never discussed. Thus, a tool that allows cross comparison of the alignment results obtained by different tools simultaneously could help a biologist evaluate their correctness and accuracy. RESULTS: In this paper, we present a versatile alignment visualization system, called SinicView, (for Sequence-aligning INnovative and Interactive Comparison VIEWer), which allows the user to efficiently compare and evaluate assorted nucleotide alignment results obtained by different tools. SinicView calculates similarity of the alignment outputs under a fixed window using the sum-of-pairs method and provides scoring profiles of each set of aligned sequences. The user can visually compare alignment results either in graphic scoring profiles or in plain text format of the aligned nucleotides along with the annotations information. We illustrate the capabilities of our visualization system by comparing alignment results obtained by MLAGAN, MAVID, and MULTIZ, respectively. CONCLUSION: With SinicView, users can use their own data sequences to compare various alignment tools or scoring systems and select the most suitable one to perform alignment in the initial stage of sequence analysis.

We use an optimization technique to accurately locate a distorted grid structure in a microarray image. By assuming that spot centers deviate smoothly from a checkerboard grid structure, we show that the process of gridding spot centers can be formulated as a constrained optimization problem. The constraint is equal to the variations of the transform parameter. We demonstrate the accuracy of our algorithm on two sets of microarray images. One set consists of some images from the Stanford Microarray Database; we compare our centers with those annotated in the Database. The other set consists of oligonucleotide images, and we compare our results with those obtained by GenePix Pro 5.0. Our experiments were performed completely automatically.

In this paper, we propose a novel framework for fast multilevel routing considering crosstalk and performance optimization. To handle the crosstalk minimization problem, we incorporate an intermediate stage of layer/track assignment into the multilevel routing framework. For performance-driven routing, we propose a novel minimum-radius minimum-cost spanning tree heuristic for global routing. Compared with the state-of-the-art multilevel routing with the routability mode, the experimental results show that our router achieved a 6.7X runtime speedup, reduced the respective maximum and average crosstalk (coupling length) by about 30% and 24%, reduced the respective maximum and average delay by about 15% and 5%. Compared with the timing-driven mode, the experimental results show that our router still achieved a 5.9X runtime speedup, reduced the respective maximum and average crosstalk by about 35% and 23%, reduced the respective maximum and average delay by about 7% and 10% in comparable routability, and resulted in fewer failed nets.

In this correspondence, we first point out an error in Jia's algorithm (1998) by a counterexample. Second, we provide a fix and make an improvement to the part of Dynamic-Join. Finally, we give an analysis and a correctness proof of our algorithm.

The traveling salesman problem is difficult to solve by traditional genetic algorithms because of the requirement that each node must be visited exactly once. In response to this critical requirement, many researchers used specialized operators to adapt traditional genetic algorithms. Although some of these operators are useful, they are ad hoc. We propose a priority-based encoding scheme instead. We assign priorities to all the edges and then perform a greedy algorithm to find a suboptimal solution. The greedy algorithm constructs a legal tour and the priority encoding makes it possible to follow traditional genetic evolution. This approach retains generality in applications and also gains remarkable experimental results.

The authors describe the use of bounded model checking (BMC) for verifying Web application code. Vulnerable sections of code are patched automatically with runtime guards, allowing both verification and assurance to occur without user intervention. Model checking techniques are relatively complex compared to the typestate-based polynomial-time algorithm (TS) we adopted in an earlier paper, but they offer three benefits - they provide counterexamples, more precise models, and sound and complete verification. Compared to conventional model checking techniques, BMC offers a more practical approach to verifying programs containing large numbers of variables, but requires fixed program diameters to be complete. Formalizing Web application vulnerabilities as a secure information flow problem with fixed diameter allows for BMC application without drawback. Using BMC-produced counterexamples, errors that result from propagations of the same initial error can be reported as a single group rather than individually. This offers two distinct benefits. First, together with the counterexamples themselves, they allow for more descriptive and precise error reports. Second, it allows for automated patching at locations where errors are initially introduced rather than at locations where the propagated errors cause problems. Results from a TS-BMC comparison test using 230 open-source Web applications showed a 41.0% decrease in runtime instrumentations when BMC was used. In the 38 vulnerable projects identified by TS, BMC classified the TS-reported 980 individual errors into 578 groups, with each group requiring a minimal set of patches for repair.

To deal with an iterative learning control problem of unknown nonlinear systems with varying initial state errors and state dependent input gain, an adaptive PID-type iterative learning controller is presented in this paper. The main design concept is motivated from a fact that a PID-type controller can be used as an approximator for an optimal controller in a compact set. The main structure of the adaptive PID-type iterative learning controller is constructed based on a time-varying boundary layer, which is designed to overcome the problem of initial state errors and further eliminate the possible undesirable chattering behavior. An error equation is then derived to represent the relation between the control input and system tracking error. Since the optimal PID gains for the best approximation is in general unavailable, the control parameters are tuned between successive iterations to ensure the stability and convergence. Compared with most of the adaptive laws in the field of adaptive iterative learning control, the proposed adaptive law can be realized without using projection or dead zone mechanism. It is shown that all the adjustable parameters and the internal signals remain bounded for all iterations, and the norm of tracking error vector at each time instant would asymptotically converge to a tunable residual set.

The World Wide Web has become a sophisticated platform capable of delivering a broad range of applications. However, its rapid growth has resulted in numerous security problems that current technologies cannot address. Researchers from both academic and private sector are devoting a considerable amount of resources to the development of Web application security scanners (i.e., automated software testing platforms for Web application security auditing) with some success. However, little is known about their potential side effects. It is possible for an auditing process to induce permanent changes in an application's state. Due to this potential, we have so far avoided large-scale empirical evaluations of our Web Application Vulnerability and Error Scanner (WAVES). we introduce a testing methodology that allows for harmless auditing, define three testing modes - heavy, relaxed, and safe modes, and report our results from two experiments. In the first, we compared the coverage and side effects of the three scanning modes using 5 real-world Web applications chosen from the 38 found vulnerable in a previous static verification effort. In the second, we used the relaxed mode to conduct a 48-hour test involving 1120 random Web sites, of which 55 were found to be vulnerable.

Security remains a major roadblock to universal acceptance of the Web for many kinds of transactions, especially since the recent sharp increase in remotely exploitable vulnerabilities have been attributed to Web application bugs. Many verification tools are discovering previously unknown vulnerabilities in legacy C programs, raising hopes that the same success can be achieved with Web applications. In this paper, we describe a sound and holistic approach to ensuring Web application security. Viewing Web application vulnerabilities as a secure information flow problem, we created a lattice-based static analysis algorithm derived from type systems and typestate, and addressed its soundness. During the analysis, sections of code considered vulnerable are instrumented with runtime guards, thus securing Web applications in the absence of user intervention. With sufficient annotations, runtime overhead can be reduced to zero. We also created a tool named.WebSSARI (Web application Security by Static Analysis and Runtime Inspection) to test our algorithm, and used it to verify 230 open-source Web application projects on SourceForge.net, which were selected to represent projects of different maturity, popularity, and scale. 69 contained vulnerabilities. After notifying the developers, 38 acknowledged our findings and stated their plans to provide patches. Our statistics also show that static analysis reduced potential runtime overhead by 98.4%.

Travel time is a fundamental measure in transportation. Accurate travel-time prediction also is crucial to the development of intelligent transportation systems and advanced traveler information systems. We apply support vector regression (SVR) for travel-time prediction and compare its results to other baseline travel-time prediction methods using real highway traffic data. Since support vector machines have greater generalization ability and guarantee global minima for given training data, it is believed that SVR will perform well for time series analysis. Compared to other baseline predictors, our results show that the SVR predictor can significantly reduce both relative mean errors and root-mean-squared errors of predicted travel times. We demonstrate the feasibility of applying SVR in travel-time prediction and prove that SVR is applicable and performs well for traffic data analysis.

A system for evaluating products in their design phase has been developed for virtual manufacturing. It is integrated into a CAD/CAM environment to calculate the cost for assembling and disassembling parts. In our earlier work, a generic assembly and disassembly model was developed to represent operations required for product manufacturing and de-manufacturing. To be useful, the model requires a method for translating high-level instructions from product designers into low-level assembly and disassembly instructions. This paper presents a set of rules for accomplishing this task. The developed rules are used for manipulating strings representing parts and handlers in binary assembly and disassembly operations. A telephone assembly and disassembly simulation is used to illustrate the developed system.

A system for evaluating products in their design phase has been developed. It is integrated into a CAD/CAM environment to calculate cost for assembling and disassembling parts. In previous work, a generic assembly and disassembly model was developed to represent operations required for product manufacturing and demanufacturing. To be useful, the model requires a method for translating high-level instructions from product designers into low-level assembly and disassembly instructions. This paper presents a set of rules for accomplishing this task. The developed rules are used for manipulating strings representing parts and handlers in binary assembly and disassembly operations. A telephone assembly and disassembly simulation is used to illustrate the developed system.

Inspired by the natural suspension capabilities in the biological limb system, a design of an active suspension system is developed for damping the undesired forces and displacements caused to vehicles by the irregularity on the road surface. The proposed controller for suspension is based on a muscular-like model fitted from the responses of different voluntary and involuntary limb movements. Because the muscular-like model emulates the property of biological damping behavior, the proposed active suspension controller has a very unique feature that will enable the controlled vehicle to adapt to varying loads and sudden impacting forces. This is in contrast to the conventional linear controller that has sensitivity and stability problems when the dynamic system is subjected to varying loads. To realize our controller, a small-scale, quarter-car model was built for our experiments on active suspension.

In this paper, we present a new approach for computing the critical area for shorts in a circuit layout. The critical area calculation is the main computational problem in very large scale integration yield prediction. The method is based on the concept of Voronoi diagrams and computes the critical area for shorts (for all possible defect radii, assuming square defects) accurately in O(n log n) time, where n is the size of the input. The method is presented for rectilinear layouts and layouts containing edges of slope /spl plusmn/1. As a byproduct, we briefly sketch how to speed up the grid method of Wagner and Koren [1995].

In this paper we present a new approach for computing the critical area for shorts in a circuit layout. The critical area calculation is the main computational problem in VLSI yield prediction. The method is based on the concept of Voronoi diagrams and computes the critical area for shorts (for all possible defect radii, assuming square defects) accurately in O(n log n) time, where n is the size of the input. The method is presented for rectilinear layouts but it is extendible to general layouts. As a byproduct we briefly sketch how to speed up the grid method of Wagner and Koren [16].

In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed efficiently (both sequentially and in parallel). We show that, after sorting the input intervals by their endpoints, a data structure can be constructed sequentially in O(n) time and O(n) space; using this data structure, each query on the length of the shortest path between any two intervals can be answered in O(1) time, and each query on the actual shortest path can be answered in O(k) time, where k is the number of intervals on that path. Furthermore, this data structure can be constructed optimally in parallel, in O(log n) time using O(n/log n) CREW PRAM processors; each query on the actual shortest path can be answered in O(1) time using k processors. Our techniques can be extended to solving the all-pair shortest path query problem on circular-arc graphs, both sequentially and in parallel, in the same complexity bounds. As an immediate consequence of our results, we improve by a factor of n the space complexity of the previously best-known sequential all-pair shortest path algorithm for unweighted interval graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 249–258, 1998

In this paper, we consider a problem related to global routing postoptimization: the crossing minimization problem (CMP). Given a global routing representation, the CMP is to minimize redundant crossings between every pair of nets. In particular, there are two kinds of CMP: constrained CMP (CCMP) and unconstrained CMP (UCMP). These problems have been studied previously where an O(m/sup 2/n) algorithm was proposed for CCMP, and where an (mn/sup 2/+/spl xi//sup 2/) algorithm was proposed for UCMP where m is the total number of modules, n is the number of nets, and /spl xi/ is the number of crossings defined by an initial global routing topology. We present a simpler and faster O(mn) algorithm for CCMP and an O[n(m+/spl xi/)] time algorithm for UCMP. Both algorithms improve over the time bounds of the previously proposed algorithms. The novel part of our algorithm is that it uses the plane embedding information of globally routed nets in the routing area to construct a graph-based framework and obtain a good junction terminal assignment that minimizes the number of crossings.

Pemmsim to make digil:lldl:[r(i topics td'Jll (Jr patl ollhis m21trlal I'or pcrsmull or classroom IIs< ,s granlc(l L,ilhiml ILCprovided 111:11 Ilw c(>p,cs 'Ire Il[>t!)l:ldL> or dislrihllt~>d till prL)til Of LXIIII 111 C1L,i:ll fi[i\l:lll!:lgC.!ht.L,~)p\,- rigJlt notic.c.(hc title ot'[he pulll Icall(l[l (l[l[i ils dole appear.and nolicc is given LIIA copyright is 11~pcmllsslon (11'llw ;\C1l.[m.'10 copy o[hcnviw, to republish.Iu pos[ on scmvrs or 10 rcdlstrilwlc 10 Iisls.rcqutl-esspccitic permission wvllor lit (Compurm]onol (;comelq, 97 N'icc I'rmlcc

Smallest rectilinear paths are rectilinear paths with simultaneous minimum numbers of bends and minimum lengths. Given two pairs of terminals within a rectilinear polygon, the authors derive an algorithm to find a pair of noncrossing rectilinear paths within the polygon such that the total number of bends and the total length are both minimized. Although a smallest rectilinear path between two terminals in a rectilinear polygon always exists, they show that such a smallest pair may not exist for some problem instances. In that case, the algorithm presented will find, among all noncrossing paths with a minimum total number of bends, a pair whose total length is the shortest, or find, among all noncrossing paths with a minimum total length, a pair whose total number of bends is minimized. They provide a simple linear time and space algorithm based on the fact that there are only a limited number of configurations of such a solution pair.

By modeling the nonlinear damping property of the biological muscle-reflex system, a neuromuscular-like controller has been proved to be capable of reflexing to any changing displacement and enhancing the compliant forces for the changing motion. The unique capability possessed by this controller presents a prominent application for designing a mechanical orthosis in aiding the limb motion of disabled people who have minimal or no voluntary control of limb muscle. To demonstrate the feasibility and effectiveness of the concept, the elbow and shoulder joints of a PUMA 560 robot were implemented with the neuromuscular-like control to emulate the limb motion.

In this paper we consider the problem of transforming a single-layer topological routing of n two-terminal nets into a rubber-band equivalent using rectilinear wires in the presence of rectilinear circuit modules. Given a topological planar VLSI layout sketch with |F| features and |W| noncrossing wire segments connecting n two-terminal nets, we present an O(|F|/spl middot/|W|) time algorithm to do the vertex-disjoint rubber-band equivalent transformation of these n nets if it exists. The algorithm consists of two phases, computing a loose homotopy with four spokes matrices, and computing a vertex-disjoint rubber-band equivalent of the given homotopy, each phase taking O(|F|/spl middot/|W|) time and space. Both complexities are asymptotically optimal in the worst case. From the vertex-disjoint rubber-band equivalent of the given homotopy, one can obtain the detailed routing within the same time complexity. Experimental results are also presented.

We consider Steiner minimal trees (SMT) in the plane where the orientations of interconnection are restricted to be either horizontal, vertical or of slopes +1 and -1. We derive a ratio, 1/4-2/spl radic/2 which we conjecture to be the Steiner ratio for 45/spl deg/-SMT. We provide a method to find an optimal 45/spl deg/-SMT for 3 or 4 points by analyzing its topological connections. For arbitrary point set of size n we present an O(n log n) time heuristic based on the notions of 45/spl deg/ minimum spanning tree and Delaunay triangulation. Empirical results compared with the rectilinear and Euclinear cases are given.

Efficient algorithms are presented for finding rectilinear collision-free paths between two given points among a set of rectilinear obstacles. The results improve the time complexity of previous results for finding the shortest rectilinear path the minimum-bend shortest rectilinear path, the shortest minimum-bend rectilinear path and the minimum-cost rectilinear path. For finding the shortest rectilinear path, a graph-theoretic approach is used and an algorithm is obtained with $O(m \log t + t \log^{3/2}t)$ running time, where t is the number of extreme edges of given obstacles and m is the number of obstacle edges. Based on this result an $O(N \log N + (m + N) \log t + (t+N) \log^{2} (t + N))$ running time algorithm for computing the $L_{1}$ minimum spanning tree of given N terminals among rectilinear obstacles is obtained. For finding the minimum-bend shortest path, the shortest minimum-bend rectilinear path, and the minimum-cost rectilinear path, we devise a new dynamic-searching approach and derive algorithms that run in $O(m \log^{2} m)$ time using $O(m \log m)$ space or run in $O(m \log^{3/2} m)$ time and space.

We consider problems of finding assorted rectilinear paths among rectilinear obstacles in a two-layer interconnection model according to the number of bends and the 1-layer distance (y-distance). Using a horizontal wave-front approach, optimal /spl theta/(e log e) time algorithms are presented to find the shortest path and the minimum-bend path using linear space, and to find the shortest minimum-bend path and the minimum-bend shortest path using O(e log e) space, where e is the number of obstacle edges. By the same approach, we also derive an algorithm for finding a shortest two-layer distance (xy-distance) minimum-bend path in optimal /spl theta/(e log e) time using O(e log e) space.>

We consider a minimax facility location problem for n points such that the facility is a line segment of a given length. The general problem can be solved by case analysis in O(n4 log n) time. When the orientation of the segment is fixed, the problem is shown to be linear-time solvable by using the prune-and-search technique. Other variations of this problem are also discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Given a point set $\rho $, a chain is a subset $\mathcal{C} \subseteq \rho $ of points in which, for any two points, one is dominated by the other. A two-chain is a subset of $\rho $ that can be partitioned into two chains. A two-chain with maximum cardinality among all possible two-chains is called a maximum two-chain. This paper presents a $\Theta ( n \log n )$ time and $\Theta ( n )$ space algorithm for finding a maximum two-chain in a point set $\rho $, where $n = | \rho |$. Maximum two-chain has applications in, for example, graph-theoretic problems, VLSI layout, and sequence manipulation.

The properties and computation of the minimum radial separation (MRS) standard for out-of-roundness are discussed. Another standard out-of-roundness measurement called the minimum area difference (MAD) center is introduced. Although the two centers have different characteristics, the approach to finding both centers shares many commonalities. An O(n log n+k) time algorithm which is used to compute the MRS center is presented. It also computes the MAD center of a simple polygon G, where n is the number of vertices of G, and k is the number of intersection points of the medial axis and the farthest-neighbor Voronoi diagram of G. The relationship between MRS and MAD is discussed.>

The problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean space is considered. The diameter of a spanning tree is the maximum distance between any two points in the tree. A characterization of an MDST is given and a $\theta (n^3)$-time algorithm for solving the problem is presented. The authors also show that for a weighted undirected graph, the problem of determining if a spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is NP-complete. The geometric Steiner minimum diameter spanning tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in $O(n)$ time.

The topological via minimization problem in a two-layer environment is considered. A set of n two-terminal nets in a bounded region is given. The authors attempt to find a homotopy to assign nets to distinct layers so that no two nets on the same layer cross each other and the number of vias is minimized. A recursive approach in which an optimal solution to a two-sided channel routing problem is used as a basis is used to solve this problem optimally. The notion of partition number K of a circle graph is introduced, and the total running time of the via minimization algorithm is shown to be O((n/K)/sup 2K-2/ log (n/K)), where n is the total number of nets.>

In this paper we study a rectilinear shortest path problem among weighted obstacles. Instead of restricting a path to totally avoid obstacles we allow a path to pass through them at extra costs. The extra costs are represented by the weights of the obstacles. We aim to find a shortest rectilinear path between two distinguished points among a set of weighted obstacles. By using a graph-theoretical approach, we obtain two algorithms which run in Ο(nlog2 n) time and Ο(n log n) space and in Ο(n log3/2 n) time and space, respectively, where n is the number of the vertices of obstacles.

The problem of finding a minimum cut of n arcs on a unit circle is considered. It is shown that this problem can be solved in $\Theta (n \log n)$ time, which is optimal to within a constant factor. If the endpoints of the arcs are sorted, the problem can be solved in linear time. The solution to the minimum cut problem can be used to solve a minimum new facility problem in competitive location and a minimum partition set problem for the intersection model of a circle graph. As a by-product it is also shown that the maximum independent set of n arcs can be obtained in linear time, assuming the endpoints are sorted, which is much simpler than the most recent result of Masuda and Nakajima [SIAMI. Comput., 17 (1988), pp. 41–52].

We consider the problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean plane. The diameter of a spanning tree is the maximum distance between any two points in the tree. We give a characterization of an MDST and present a θ(n3 time algorithm for solving the problem. We also show that for a weighted undirected graph, the problem of determining if a spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is N P-complete. The geometrical minimum diameter Steiner tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in Ο(n) time.

It is shown how a mathematical constraint resolution (MATHCORE) system can be used to design a better decision support system. MATHCORE not only has the flexibility of expressing mathematical equations within a logic programming paradigm in a natural way, but also has an ability to deal with systems of nonlinear equations, regression analysis, and optimization problems. While most existing constraint logic programming systems try to devise their own constraint solvers and are confined to systems of linear equations and simple nonlinear functions, the MATHCORE removes this limitation by directly taking advantage of well-developed numerical methods available in the mathematical libraries. With MATHCORE, complex decision optimization models can be embedded in a rule-based decision support system. Using this methodology, it is demonstrated that the interactions among various economic factors in a housing market can be stated in the program body, while various (optimization) goals of social welfare can be expressed as queries.>

A topological via minimization problem in a two-layer routing environment is examined. The problem of minimizing the number of vias needed to route n two-terminal nets in a bounded routing region is shown to be NP-hard. However, in the case of a two-shore routing region, the topological via minimization problem can be solved in O(n/sup 2/ log n) time. As a basis for the algorithm, a two-chain maximum dominance problem, which is of interest in its own right, is considered, and its applications to other very large-scale integration layout problems are shown.>

This paper describes a new alorithm for clipping a line in two dimensions against a rectangular window. This algorithm avoids computation of intersection points which are not endpoints of the output line segment. The performance of this algorithm is shown to be consistently better than existing algorithms, including the Cohen-Sutherland and Liang-Barsky algorithms. This performance comparison is machine-independent, based on an analysis of the number of arithmetic operations and comparisons required by the different algorithms. We first present the algorithm using procedures which perform geometric transformations to exploit symmetry properties and then show how program transformation techniques may be used to eliminate the extra statements involved in performing geometric transformations.

We consider the following problem: Given a rectangle containing N points, find the largest area subrectangle with sides parallel to those of the original rectangle which contains none of the given points. If the rectangle is a piece of fabric or sheet metal and the points are flaws, this problem is finding the largest-area rectangular piece which can be salvaged. A previously known result [13] takes $O(N^2 )$ worst-case and $O(N\log ^2 N)$ expected time. This paper presents an $O(N\log ^3 N)$ time, $O(N\log N)$ space algorithm to solve this problem. It uses a divide-and-conquer approach similar to the ones used by Bentley [1] and introduces a new notion of Voronoi diagram along with a method for efficient computation of certain functions over paths of a tree.

We study the computational complexity of the art gallery problem originally posed by Klee, and its variations. Specifically, the problem of determining the minimum number of vertex guards that can see ann-wall simply connected art gallery is shown to be NP-hard. The proof can be modified to show that the problems of determining the minimum number of edge guards and the minimum number of point guards in a simply connected polygonal region are also NP-hard. As a byproduct, the problem of decomposing a simple polygon into a minimum number of star-shaped polygons such that their union is the original polygon is also shown to be NP-hard.

We address ourselves to an instance of the Shortest Path problem with obstacles where a shortest path in the Manhattan (or L1) distance is sought between two points (source and destination) and the obstacles are n disjoint rectangles with sides parallel to the coordinate axes. A plane sweep technique is applied rather than the graph theoretic approach frequently used in the literature. We show that there has to be a path of minimum length between the two given points which is monotone in at least one of x or y directions. Then we present an algorithm of time complexity Ο(n log n) for constructing that path and show that our algorithm is optimal.

The one-dimensional on-line bin-packing problem is considered, A simple O (1)-space and O ( n )-time algorithm, called HARMONIC M , is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O ( n )-space and O ( n log n )-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0 (1)-space on-line bin-packing algorithms. Finally a revised version of HARMONIC M , an O ( n )-space and O ( n )- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.

Abstract In this paper we address the problem of constructing a Euclidean shortest path between two specified points (source, destination) in the plane, which avoids a given set of barriers. This problem had been solved earlier for polygonal obstacles with the aid of the visibility graph. This approach however, has an Ω(n 2 ) time lower bound, if n is the total number of vertices of the obstacles. Our goal is to find interesting cases for which the solution can be obtained without the explicit construction of the entire visibility graph. The two cases are (i) the path must lie within an n‐vertex simple polygon; (ii) the obstacles are n disjoint and parallel line segments. In both instances greedy O(n log n) time algorithms can be developed which solve the problems by constructing the shortest‐path tree from the source to all the vertices of the obstacles and to the destination.

We consider the 2-dimensional channel assignment problem: given a set S of iso-oriented rectangles (whose sides are parallel to the coordinate axes), find a minimum number of planes (channels) to which only nonoverlapping rectangles are assigned. This problem is equivalent to the coloring problem of the rectangle intersection graph G = (V, E), in which each vertex in V corresponds to a rectangle and two vertices are adjacent iff their corresponding rectangles overlap, and we ask for an assignment of a minimum number of colors to the vertices such that no adjacent vertices are assigned the same color. We show that the problem is NP-hard.

We survey the state of the art of computational geometry, a discipline that deals with the complexity of geometric problems within the framework of the analysis of algorithms. This newly emerged area of activities has found numerous applications in various other disciplines, such as computer-aided design, computer graphics, operations research, pattern recognition, robotics, and statistics. Five major problem areas—convex hulls, intersections, searching, proximity, and combinatorial optimizations—are discussed. Seven algorithmic techniques—incremental construction, plane-sweep, locus, divide-and-conquer, geometric transformation, prune-and-search, and dynamization—are each illustrated with an example. A collection of problem transformations to establish lower bounds for geo-metric problems in the algebraic computation/decision model is also included.

This paper uses a new formulation of the notion of duality that allows the unified treatment of a number of geometric problems. In particular, we are able to apply our approach to solve two long-standing problems of computational geometry: one is to obtain a quadratic algorithm for computing the minimum-area triangle with vertices chosen among n points in the plane; the other is to produce an optimal algorithm for the half-plane range query problem. This problem is to preprocess n points in the plane, so that given a test half-plane, one can efficiently determine all points lying in the half-plane. We describe an optimal O(k + log n) time algorithm for answering such queries, where k is the number of points to be reported. The algorithm requires O(n) space and O(n log n) preprocessing time. Both of these results represent significant improvements over the best methods previously known. In addition, we give a number of new combinatorial results related to the computation of line arrangements.

A new dynamizing technique is introduced wherebynpoint Voronoi diagrams (both closest and farthest point) can be updated inO(n)time per insertion or deletion, in the worst case. General properties of these dynamic Voronoi diagrams are explored including a storage/ deletion-time trade-off. In addition, their application to such problems as nearest neighbor search and the 2-minimum spanning circle problem is discussed.

Abstract We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.

The medial axis transformation is a means first proposed by Blum to describe a shape. In this paper we present a 0(n log n) algorithm for computing the medial axis of a planar shape represented by an n-edge simple polygon. The algorithm is an improvement over most previously known results interms of both efficiency and exactness and has been implemented in Fortran. Some computer-plotted output of the program are also shown in the paper.

In this paper we consider the generating, ranking, and unranking of 2-3 trees with n keys. We propose a linear ordering among these trees. The problem of ranking is to determine the rank of a given tree in this ordering, while unranking means constructing the tree of a given rank. The main result is that ranking and unranking can be done in $O(n)$ time after a preprocessing step that takes $O(n^2 )$ time and space.

The notion of Voronoi diagram for a set of N points in the Euclidean plane is generalized to the Voronoi diagram of order k and an iterative algorithm to construct the generalized diagram in 0(k2N log N) time using 0(k2(N − k)) space is presented. It is shown that the k-nearest neighbor problem and other seemingly unrelated problems can be solved efficiently with the diagram.

For the convex polygon P having n vertices entirely contained in a convex polygon K having m vertices, an optimal algorithm with running time O(n + m) is presented to compute and name regions in the boundary of K from which it is possible to illuminate the exterior of P. It is also shown that this illumination region algorithm can be used to improve the worst case O(nm) running time of a related two dimensional simplex coverability algorithm so that it too has running time O(n + m), and is thus optimal to within a constant factor.

Given an arbitrary simple polygon with N vertices we present an algorithm for shading the interior of the polygon with a set of parallel lines where the slope and the distance between lines are prespecified. If the number of shading line segments is M, the algorithm described in the paper runs in 0(N log N + M) time. The algorithm is generalizable to shade any region or regions of an arbitrary planar subdivision.

Abstract An O ( n log n ) heuristic for the Euclidean Steiner Minimal Tree (ESMT) problem is presented. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the Delaunay triangulation, then “recomposes” the suboptimal Steiner Minimal Tree (SMT) according to the Voronoi diagram and Minimum Spanning Tree (MST) of the point set. The ESMT algorithm was implemented in FORTRAN‐IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the O ( n log n ) algorithm with an O ( n 4 ) algorithm clearly indicates that the O ( n log n ) algorithm is as good as the previous O ( n 4 ) algorithm in achieving reductions in the ratio SMT/MST of the given vertex set. This is somewhat surprising since the O ( n 4 ) algorithm considers more potential Steiner points and alternative tree configurations.

In this paper we study the Voronoi diagram for a set of N line segments and circles in the Euclidean plane. The diagram is a generalization of the Voronoi diagram for a set of points in the plane and has applications in wire layout, facility location, clustering and contouring problems. We present an $O(N(\log N)^2 )$ algorithm for constructing the diagram. It is an improvement of a previous known result which takes $O(Nc^{\sqrt {\log N} } )$ time. The algorithm described in this paper is also shown to be applicable under a more general metric if certain conditions are satisfied.

Two generic record-permutation bubble devices—the bubble ladder and the bubble string comparator—have been reported in the literature but not yet implemented. The former relies on the extensive use of external control lines, while the latter relies solely on the interaction between bubbles. The ladder has evolved into an odd- even sorter and then a rebound sorter, but, uufortunately, it is operated by a large number of control lines. This paper shows that equally efficient but more versatile sorters can be constructed from the bubble string comparators without the control lines. Moreover, the new sorter—an up-down sorter—will be implemented in the recently invented high-density, high-speed, coil-less perforated-sheet bubble devices.

The Voronoi diagram, also known as the Thiessen diagram, for a set of N points in the Cartesian plane in which the L,-metnc is the distance measure, where p is a real number between 1 and 0o inclusive, is defined, and an algorithm for constructing the dmgram m O(NlogN) tune is presented This algonthm uses the divide-and-conquer technique.Many proximity problems revolving a set of points, such as finding the nearest neighbor of a given point, finding the minimum spamung tree, findmg the smallest circle (m the Lp-metric) enclosing the point set, etc., can be solved very efficiently via the diagram The running time of the algorithm presented is also shown to be optimal to within a constant factor.

In this paper we study the problem of scheduling the read/write head movement to handle a batch of $nI/O$ requests in a 2-dimensional secondary storage device in minimum time. Two models of storage systems are assumed in which the access time of a record (being proportional to the “distance” between the position of the record and that of the read/write head) is measured in terms of $L_1 $ and $L_\infty $ metrics, respectively. The scheduling problem, referred to as the Open Path Problem (OPP), is equivalent to finding a shortest Hamiltonian path with a specified end point in a complete graph with n vertices. We first show in this paper that there exists a natural isometry between the $L_1 $ and $L_\infty $ metrics. Consequently, the existence of a polynomial time algorithm for the OPP in one metric implies the existence of a polynomial time algorithm for the same problem in the other metric. Based on a result by Garey, Graham and Johnson, it is easy to show that the OPP in $L_1 $ (hence in $L_\infty $) metric is $NP$-complete. A heuristic to solve the OPP is therefore presented. It is based on a geometric structure called the Voronoi diagram in $L_1 $ metric. An optimal (worst-case) algorithm of time complexity $O(n\log n)$ for constructing the diagram for a set of n points in a plane is described. Using this diagram one can build a near-optimal path through each point either by constructing a minimum spanning tree or by the closest insertion method. Both algorithms are shown to take $O(n\log n)$ time which is the time for the construction of the diagram and yield an approximate solution within a factor of 2. The bound is also shown to be tight in the worse case. For the average case, simulation results show that the minimum spanning tree approach is better than the closest insertion method. As expected, they are far better than the sequential one in which the request is processed one at a time on the first-come–first-served basis.

article Free Access Share on Quintary trees: a file structure for multidimensional datbase sytems Authors: D. T. Lee Northwestern Univ., Evanston, IL Northwestern Univ., Evanston, ILView Profile , C. K. Wong IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims ACM Transactions on Database SystemsVolume 5Issue 3Sept. 1980 pp 339–353https://doi.org/10.1145/320613.320618Published:01 September 1980Publication History 64citation559DownloadsMetricsTotal Citations64Total Downloads559Last 12 Months29Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The kernel K(P) of a simple polygon P wah n verUces is the locus of the points internal to P from which all verUces of P are wslble Equwalently, K(P) is the mtersectmn of appropriate half-planes determined by the polygon's edges Although it is known that to find the intersection of n generic half-planes requires time O(n log n), we show that one can exploit the ordering of the half-planes corresponding to the sequence of the polygon's edges to obtain a kernel finding algorithm which runs m time O(n) and is therefore optimal

Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We exhibit a Θ(N log N) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling.

Given a subdivision of the plane induced by a planar graph with n vertices, in this paper we consider the problem of identifying which region of the subdivision contains a given test point. We present a search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure. The search runs in time at most $O((\log n)^{2})$, while the preprocessing task runs in time at most $O(n \log n)$ and requires $O(n)$ storage. The methods are quite general, since an arbitrary subdivision can be transformed in time at most $O(n \log n)$ into one to which the preprocessing procedure is applicable. This solution of the point location problem yields interesting and efficient solutions of other geometric problems, such as spatial convex inclusion and inclusion in an arbitrary polygon.

Given a subdivision of the plane induced by a planar graph with n vertices, in this paper the problem of identifying which region of the subdivision contains a given test points is considered. A search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure is presented. The search runs in time at most O((log n)2), while the preprocessing task runs in time at most O(n log n) and requires O(n) storage. The methods are quite general, since an arbitrary subdivision can be transformed in time at most O(n log n) into one to which the preprocessing procedure is applicable. This solution of the point location problem yields interesting and efficient solutions of other geometric problems, such as spatial convex inclusion and inclusion in an arbitrary polygon

It is well known that any switching function may be transformed into a completely symmetric function when repetition of the input variables is allowed. We present an algorithm that may be applied to reduce the number of repeated variables when the transformation is performed. The method is based on an iterative construction of symmetric functions by admitting an increasing number of variables towards a completely symmetric function. The algorithm produces a near minimal number of the total number of inputs in the resultant symmetric function. This algorithm can also be used to determine all partially symmetric variable sets of a given function.