Simple algorithms for searching a polygon with flashlights

The k-searcher is a mobile guard whose visibility is limited to k rays emanating from her position, where the direction of each ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P, is it possible for the k-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P? We present O(n²)-time algorithms for constructing a search schedule of the 1-searcher and the 2-searcher, respectively. Our framework for the 1-searcher can be viewed as a modification of that of LaValle et al. [Proc. 16th ACM Symp. on Computational Geometry, 2000, pp. 260-269] and is naturally extended for the 2-searcher.     

New Engineered Particles from Spray Dryers: Research Needs in Spray Drying

This article reviews developments in the simulations of spray dryer behavior, including the challenges in modeling the complex flow patterns inside the equipment, which are often highly transient and three-dimensional in nature. There appears to be considerable scope for using CFD simulations for investigating methods to reduce the rates of wall deposition and of thermal degradation for particles by modifying the air flow patterns in the chamber through small changes in the air inlet geometry. Challenges include building particle drying kinetics and reaction processes, as well as agglomeration behavior, into these simulations. The numerical simulations should be valuable supplements to pilot-scale testing, enabling more extensive and accurate optimization to be carried out than hitherto possible. New understanding of reaction processes and materials science, in combination with recent knowledge of the application of CFD to these problems, may enable new engineered powder products to be developed from the one-step spray-drying process.     

Profile-Based Linguistic Uniformity as a Generic Method for Comparing Language Varieties

In this text we present``profile-based linguistic uniformity', a methoddesigned to compare language varieties on thebasis of a wide range of potentiallyheterogeneous linguistic variables. In manyrespects a parallel can be drawn with currentmethods in dialectometry (for an overview, see,Nerbonne and Heeringa, 2001; Heeringa, Nerbonneand Kleiweg, 2002): in both casesdissimilarities between varieties on the basisof individual variables are summarized inglobal dissimilarities, and a series oflanguage varieties are subsequently clusteredor charted using multivariate techniques suchas cluster analysis or multidimensionalscaling. This global similarity between themethods makes it possible to compare them andto investigate the implications of notabledifferences. In this text we specifically focuson, and defend one characteristic of ourmethodology, its profile-based nature.     

Two Isomers of C60F48: Computed Inter-isomeric Equilibrium

C₆₀F₄₈ has been known to exist in two isomeric forms of D₃ and S₆ symmetries. However, the quantum-chemical calculations have not agreed on their stability order though a near-isoenergetic picture is otherwise always encountered. In order to clarify the situation, the entropy effects are evaluated for synthetic temperatures of about 500K. The entropy evaluations suggest that the D₃ isomer should be more stable in the potential energy by 2.05-2.55 kcal/mol (to which term the ab initio data are closer than the semiempirical ones).     

CAM中一类新的NP完全问题

本文提出了计算机辅助制造(CAM)中的一类作业调度问题并证明了它的NP完全性。     

PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs are a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. Recent work on learning PDFAs from random examples has used the KL-divergence as the error measure; here we use the variation distance. We build on recent work by Clark and Thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.     

A Dynamic Dictionary for Priced Information with Application

In this paper we design a dynamic dictionary for the priced information model initiated by Charikar et al. Assume that a set S consisting of n elements is given such that each element has an associated price, a positive real number. The cost of performing an operation on elements of S is a function of their prices. The cost of an algorithm is the sum of the costs of all operations it performs. The objective is to design algorithms which incur low cost. In this model we propose a dynamic dictionary, supporting search, insert and delete, for keys drawn from a linearly ordered set. As an application we show that the dictionary can be used in computing the trapezoidal map of a set of line segments, a fundamental problem in computational geometry.     

A visual tool for computer supported learning: The robot motion planning example

We introduce an effective computer aided learning visual tool (CALVT) to teach graph-based applications. We present the robot motion planning problem as an example of such applications. The proposed tool can be used to simulate and/or further to implement practical systems in different areas of computer science such as graphics, computational geometry, robotics and networking. In the robot motion planning example, CALVT enables users to setup the working environment by creating obstacles and a robot of different shapes, specifying starting and goal positions, and setting other path or environment parameters from a user-friendly interface. The path planning system involves several phases. Each of these modules is complex and therefore we provide the possibility of visualizing graphically the output of each phase. Based on our experience, this tool has been an effective one in classroom teaching. It not only cuts down, significantly, on the instructor’s time and effort but also motivates senior/graduate students to pursue work in this specific area of research.     

A note on the Consecutive Ones Submatrix problem

A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer K is given and we want to know if there exists a submatrix B of A consisting of K columns of A with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by Garey and Johnson [Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979].