TRACING A PLANAR ALGEBRAIC CURVE

In this paper, an algorithm that determines a real algebraic curve is outlined. Its basicstep is to divide the plane into subdomain1s that include only simple branches of the algebraic curvewithout singular points. Each of the branches is then stably and efficiently traced in the particularsubdomain. Except for tracing, the algorithm requires only a couple of simple operations on poly-nomials that ran be carried out exacrly if the coefficients are rational, and the determination of the real roots of several univariate polynomials.     

A continuous-time linear complementarity system for dynamic user equilibria in single bottleneck traffic flows

This paper formally introduces a linear complementarity system (LCS) formulation for a continuous-time, multi-user class, dynamic user equilibrium (DUE) model for the determination of trip timing decisions in a simplified single bottleneck model. Existence of a Lipschitz solution trajectory to the model is established by a constructive time-stepping method whose convergence is rigorously analyzed. The solvability of the time-discretized subproblems by Lemke’s algorithm is also proved. Combining linear complementarity with ordinary differential equations and being a new entry to the mathematical programming field, the LCS provides a computational tractable framework for the rigorous treatment of the DUE problem in continuous time; this paper makes a positive contribution in this promising research venue pertaining to the application of differential variational theory to dynamic traffic problems.     

On-line user languages

The principal differences between on-line and off-line user languages are discussed in some detail. The characteristic features of the OPL programming language are mentioned together with experiences of Project MAC, pointing at increased efficiency in the use of computers.Work reported herein was supported by Project MAC, and M. I. T. research program sponsored by the Advanced Research Projects Agency, Department of Defense, under Office of Naval Research contract NONR-4102(01). Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Reducing the graphical user interface of a dynamic geometry system

Graphical user interfaces (GUIs) of dynamic or interactive geometry software (DGS) allow users to interact with the DGS by using a computer mouse. Clicking on a GUI icon performs an action like choosing a construction tool or manipulating an object. For novices, it may be difficult to recognize and recall the icons needed for a task. Learning mathematics and learning the use of a dynamic geometry system at the same time could lead to cognitive overload. Several DGS systems try to solve this problem by offering different GUIs: expert users can choose between a wide range of icons, while for novice users only the most basic icons are presented. By preselecting a specific set of icons, a teacher can adapt a DGS to create a tool, which meets specific pedagogical demands. Two experiments were conducted to investigate the effects of reducing GUIs of a DGS. In experiment 1, which was carried out with full and reduced interfaces of the DGS Cinderella, the eye movements and gaze points of the users were recorded by an eye tracker. The time taken by users to find given icons in different types of interfaces was measured. In experiment 2, students measured the angle sums of polygons using the DGS Cinderella with a full or a reduced interface. No significant effects of GUI reduction were found in both experiments. The results are discussed and ideas for future research are presented.     

Academic inventory systems programs structured on a user command language

Eleven deterministic and probabilistic Inventory Systems BASIC computer programs, useful in academic and research environments, are described. All accept identical conversational instructions in a unified user command language. Each program has help and examples messages, and built-in sets of data useful for illustration. It accepts commands for retrieving, displaying, and changing the data, and for computing and minimization. Two programs also accept simulation commands. The availability of the source code and detailed documentation allows users to modify the programs, delete or add algorithms, change dimensions, and to translate the programs into other languages.     

Academic operations research programs structured on a user command language

Twelve deterministic and probabilistic Operations Research BASIC computer programs, useful in academic and research environments, are described. All accept identical conversational instructions in a unified user command language. Each program has help and examples messages, and built-in sets of data useful for illustration. It accepts commands for retrieving, displaying, changing, and saving the data, and for computing and optimization. Three programs also accept simulation commands. The availability of the source code and detailed documentation allows users to modify the programs, delete or add algorithms, change dimensions, and to translate the programs into other languages.     

逐点伪轨跟踪性质与混沌

本文研究了逐点伪轨跟踪性质与拓扑混合等混沌性态的关系,给出了$f$具有逐点伪轨跟踪性质时,$f$具有一致正熵和完全正熵的一些等价条件.     

About Tracing Problems in Dynamic Geometry

Dynamic Geometry is the field of interactively performing geometric construction on a computer. In addition to simulating ruler-and-compass constructions we allow a drag mode. This drag mode allows to move geometric objects that have at least one degree of freedom. The remaining part of the construction should adjust automatically. Thus, during the motion, we have to trace the resulting paths of all geometric objects. This path tracking problem is known as the Tracing Problem from Dynamic Geometry. It combines the step-by-step procedure of doing geometric constructions with the continuous concept of motions. This study is based on the model for Dynamic Geometry used in the interactive geometry software Cinderella. We give a numerical solution to the Tracing Problem based on continuation methods and a reliable algorithm based on real and complex interval arithmetic. Degenerate situations like the intersection of two identical lines lead to critical points in the configuration space and are treated separately.     

Tracing Compressed Curves in Triangulated Surfaces

A simple path or cycle in a triangulated surface is normal if it intersects any triangle in a finite set of arcs, each crossing from one edge of the triangle to another. A normal curve is a finite set of disjoint normal paths and normal cycles. We describe an algorithm to “trace” a normal curve in $O(\min \{ X, n^2\log X \})$ O ( min { X , n 2 log X } ) time, where $n$ n is the complexity of the surface triangulation and $X$ X is the number of times the curve crosses edges of the triangulation. In particular, our algorithm runs in polynomial time even when the number of crossings is exponential in $n$ n . Our tracing algorithm computes a new cellular decomposition of the surface with complexity $O(n)$ O ( n ) ; the traced curve appears in the 1-skeleton of the new decomposition as a set of simple disjoint paths and cycles. We apply our abstract tracing strategy to two different classes of normal curves: abstract curves represented by normal coordinates, which record the number of intersections with each edge of the surface triangulation, and simple geodesics, represented by a starting point and direction in the local coordinate system of some triangle. Our normal-coordinate algorithms are competitive with and conceptually simpler than earlier algorithms by Schaefer et al. (Proceedings of 8th International Conference Computing and Combinatorics. Lecture Notes in Computer Science, vol. 2387, pp. 370–380. Springer, Berlin 2002; Proceedings of 20th Canadian Conference on Computational Geometry, pp. 111–114, 2008) and by Agol et al. (Trans Am Math Soc 358(9): 3821–3850, 2006).     

逐点伪轨跟踪性质及其应用

本文给出紧致度量空间逐点伪轨跟踪性质的定义,该定义是伪轨跟踪性质定义的推广.作为应用,证明如下结论:(i)若f具有逐点伪轨跟踪性质,且对任意k∈Z ,fk为链转换的,那么对任意k∈Z ,fk为开集转换;(ii)若f具有逐点伪轨跟踪性质,且对任意n∈Z ,fn为链转换的,则f具有初始敏感依赖性质;(iii)若f为开集混合的,且具有逐点伪轨跟踪性质,那么f具有性质P;(iv)设f:(X,d)→(X,d)是同胚映射,那么f具有逐点伪轨跟踪性质当且仅当移位映射σf具有逐点伪轨跟踪性质.     

序列伪轨跟踪性与拓扑可迁

给出序列伪轨跟踪性的定义,得到拓扑可迁的一个充分条件,并证明,若f是同胚,则f具有序列伪轨跟踪性当且仅当其逆极限空间上的移位映射σf具有序列伪轨跟踪性。     

Locating a single facility and a high-speed line

In this paper we study a facility location problem in the plane in which a single point (facility) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time from the clients to the facility, using the _L1$L_1$ or Manhattan metric. The rapid transit line is given by a segment with any length and orientation, and is an alternative transportation line that can be used by the clients to reduce their travel time to the facility. We study the variant of the problem in which clients can enter and exit the highway at any point. We provide an O(n³)$O(n^3)$-time algorithm that solves this variant, where n is the number of clients. We also present a detailed characterization of the solutions, which depends on the speed given along the highway.     

Performance evaluation of a single queue capable of handling two like jobs as a single entity

In this paper, we model an open queuing network and analyze performance measures with and without feedback as two individual cases. The model comprises a single queue with a dedicated processor capable of handling two like jobs as a single job. Two different job arrivals with different processing times are considered with an internal timer. Performance measures such as average queue length, average response time, average waiting time of the jobs are computed and plotted. The joint density function for the inter arrival time and arrival rate are derived. The probability mass function has been derived for all possible cases that may arise in a duration (0, t], considering n job arrivals during that period of time and an integer programming problem is formulated to obtain optimal sequence patterns which would maximize the efficiency of the model.     

Semiregular surfaces with a single triple-point

We exhibit 18 surfaces that can be mapped generically into 3-space with a single triple-point. The family should be used as a source of examples and counter-examples.     

An N-path user equilibrium for transportation networks

The traditional trip-based approach to transportation modeling has been employed for the past decade. The last step of the trip-based modeling approach is traffic assignment, which has been typically formulated as a user equilibrium (UE) problem. In the conventional perspective, the definition of UE traffic assignment is the condition that no road user can unilaterally change routes to reduce their travel time. An equivalent definition is that the travel times of all the used paths between any given origin–destination pair are equal and less than those of the unused paths. The underlying assumption of the UE definition is that road users have full information on the available transportation paths and can potentially use any path if the currently used path is overly congested. However, a more practical scenario is that each road user has a limited path set within which she/he can choose routes from. In this new scenario, we call the resulting user equilibrium an N-path user equilibrium (NPUE), in which each road user has only N paths to select from when making route choices in the network. We introduce a new formulation of the NPUE and derive optimality conditions based on this formulation. Different from traditional modeling framework, the constraints of the proposed model are of linear form, which makes it possible to solve the problem with conventional convex programming techniques. We also show that the traditional UE is a special case of an NPUE and prove the uniqueness of the resulting flow pattern of the NPUE. To efficiently solve this problem, we devise path-based and link-based solution algorithms. The proposed solution algorithms are empirically applied to networks of various sizes to examine the impact of constrained user path sets. Numerical results demonstrate that NPUE results can differ significantly from UE results depending on the number of paths available to road users. In addition, we observed an interesting phenomenon, where increasing the number of paths available to road users can sometimes decrease the overall system performance due to their selfish routing behaviors. This paradox demonstrates that network information should be provided with caution, as such information can do more harm than good in certain transportation systems.     

Tracing fourth graders’ learning of fractions: early episodes from a year-long teaching experiment

Considerable and significant research¹ has been conducted focusing on what students know about fraction ideas.² However, much of the research looks at student understanding following some instruction. The research³ reported in this paper differs from other studies in three significant ways: (1) the students were 9- and 10-year-old fourth graders; (2) they had not yet had an introduction to operational rules and definitions about fractions; and (3) the research design emphasized a student-centered approach. The research is based on the view that given particular conditions in which students are invited to work together and conduct thoughtful investigations with appropriate materials, they can build fundamental mathematical ideas.