Stabbers of line segments in the plane

The problem of computing a representation of the stabbing lines of a set S of segments in the plane was solved by Edelsbrunner et al. We provide efficient algorithms for the following problems: computing the stabbing wedges for S, finding a stabbing wedge for a set of parallel segments with equal length, and computing other stabbers for S such as a double-wedge and a zigzag. The time and space complexities of the algorithms depend on the number of combinatorially different extreme lines, critical lines, and the number of different slopes that appear in S.     

Developing Prospective Elementary Teachers' Flexibility in the Domain of Proportional Reasoning

Flexibility in the use of mathematics procedures consists of the ability to employ multiple solution methods across a set of problems, solve the same problem using multiple methods, and choose strategically from among methods so as to reduce computational demands. The purpose of this study was to characterize prospective elementary teachers' (n = 148) flexibility in the domain of proportional reasoning before formal instruction and to test the effects of two versions of an intervention that engaged prospective teachers in comparing different solutions to proportion problems. Results indicate that (a) participants exhibited limited flexibility before formal instruction, (b) the intervention led to significant gains in participants' flexibility that were retained six months after instruction, and (c) varying the source of the problem solutions that participants compared had no discernible effects on their flexibility. Implications for mathematics teacher preparation and for research on flexibility development are provided.     

Ramsey-type constructions for arrangements of segments

Improving a result of Károlyi, Pach and Tóth, we construct an arrangement of n segments in the plane with at most n^log8/log169 pairwise crossing or pairwise disjoint segments. We use the recursive method based on flattenable arrangements which was established by Larman, Matoušek, Pach and Tör?csik.     

Computing simple circuits from a set of line segments

We address the problem of connecting line segments to form the boundary of a simple polygon—a simple circuit. However, not every set of segments can be so connected. We present anO(n logn)-time algorithm to determine whether a set of segments, constrained so that each segment has at least one endpoint on the boundary of the convex hull of the segments, admits a simple circuit. Furthermore, this technique can also be used to compute a simple circuit of minimum perimeter, or a simple circuit that bounds the minimum area, with no increase in computational complexity.     

AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments

LetX be a given set ofn circular and straight line segments in the plane where two segments may interest only at their endpoints. We introduce a new technique that computes the Voronoi diagram ofX inO(n logn) time. This result improves on several previous algorithms for special cases of the problem. The new algorithm is relatively simple, an important factor for the numerous practical applications of the Voronoi diagram.This work was supported by NSF Grants No. DCR-84-01898 and No. DCR-84-01633.     

Capacity and price setting for dispersed,time-sensitive customer segments

We consider joint pricing and capacity decisions for a facility serving heterogeneous consumers that span a continuous range of locations, and are sensitive to time delays. Within this context, we analyze two contrasting service strategies: segmentation and pooling. Consumer segments differ with respect to their reservation prices and time sensitivities, and are dispersed over a single distance dimension. The firm serves these consumers using a process that we initially model as an M/M/1 queuing system. We analyze profit-maximizing price and capacity levels for a monopolist, and contrast the optimal segmentation and pooling policies. We find that when consumers are time sensitive, and can expect queuing delays at the firm’s facility (due to random arrival and service times), then scale economies from pooling can outweigh segmentation benefits. Yet, segmentation outperforms pooling when consumer segments differ substantively, in which case the firm can use capacity as a lever to price discriminate between the segments. Moreover, by contrasting a dedicated-services strategy, which directly targets specific segments and serves them separately, with the alternative of allowing consumers to self-select, we find that self-selection has a moderate negative influence on profits. We also examine the profit impact of employing alternative queuing systems, and find that a hybrid strategy based on a prioritized queuing discipline, that combines elements of segmentation (by offering different waiting times) and pooling (by sharing capacity across consumer segments), can outperform both the pure segmentation and pooling strategies.     

Implicitly representing arrangements of lines or segments

Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n ²) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space¹ and (n ^3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n ^1/3)+O(K) time, given(n ^4/3) space and (n ^5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m ^2/3 n ^2/3+n), which is nearly optimal.The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fifth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. The sixth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the non-DEC authors were visiting at the DEC Systems Research Center.     

Arrangements of segments that share endpoints: Single face results

We provide new combinatorial bounds on the complexity of a face in an arrangement of segments in the plane. In particular, we show that the complexity of a single face in an arrangement ofn line segments determined byh endpoints isO(h logh). While the previous upper bound,O(nα(n)), is tight for segments with distinct endpoints, it is far from being optimal whenn=Ω(h ²). Our results show that, in a sense, the fundamental combinatorial complexity of a face arises not as a result of the number ofsegments, but rather as a result of the number ofendpoints. The research of E. M. Arkin was partially supported by NSF Grants ECSE-8857642 and CCR-9204585. K. Kedem's research was partially supported by AFOSR Grant AFOSR-91-0328. The research of J. S. B. Mitchell was partially supported by a grant from Boeing Computer Services, Hughes Research Laboratories, AFOSR Grant AFOSR-91-0328, and by NSF Grants ECSE-8857642 and CCR-9204585.     

Performance modeling and optimization of networks of bridged LANs

An internetwork of LANs is modeled as a graph with LAN segments as edges and transparent bridges and repeaters as nodes. The graph model leads to a simple expression for the effective load on an arbitrary LAN segment, which takes into account the overhead traffic due to the learning mechanism of the transparent bridges. Simplifying assumptions for the operation of the MAC layer protocol lead to a simple expression for the average end-to-end delay in terms of the effective loads on the LAN segments.The problem of optimally locating bridges and repeaters on the nodes in order to minimize the average delay is then studied. It is shown that this problem is equivalent to the set partitioning problem, which is NP-complete, but for which good algorithms exist to solve large problems. The related problem of minimizing cost subject to a constraint on average end-to-end delay is also discussed. Finally, the problem of locating bridges and repeaters on a linear topology, as typically found in an office building with a large number of floors, is studied. This special case gives rise to anO(L ²) algorithm, whereL is the number of floors.Supported partially through AT&T grant 5-23690.     

Concentration Problems for Bandpass Filters in Communication Theory over Disjoint Frequency Intervals and Numerical Solutions

The concentration problem of maximizing signal strength of bandlimited and timelimited nature is important in communication theory. In this paper we consider two types of concentration problems for the signals which are bandlimited in disjoint frequency-intervals, which constitute a band-pass filter. For the first type the problem is to determine which members of L ²(−∞,∞) lose the smallest fraction of their energy when first timelimited and then bandlimited. For the second type the problem is to determine which bandlimited signals lose the smallest fraction of their energy when restricted to a given time interval. For both types of problems, basic theoretical properties and numerical algorithms for solution and convergence theorems are given. Orthogonality properties of analytically extended eigenfunctions over L ²(−∞,∞) are also proved. Numerical computations are carried out which corroborate the theory. Relationship between eigenvalues of these two types of problems is also established. Several properties of eigenvalues of both types of problems are proved.     

Digitalizing line segments

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments, thus giving an explicit construction that resolves the main question of [J. Chun, M. Korman, M. Nöllenburg, and T. Tokuyama. Consistent digital rays. Discrete Comput. Geom., 42(3):359–378, 2009].     

Minimum decomposition of a digital surface into digital plane segments is NP-hard

This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPSs for short). We prove that the decision problem (does there exist a decomposition with less than λ DPSs?) is NP-complete, and thus that the optimization problem (finding the minimum number of DPSs) is NP-hard. The proof is based on a polynomial reduction of any instance of the well-known 3-SAT problem to an instance of the digital surface decomposition problem. A geometric model for the 3-SAT problem is proposed.     

Initial segments of computable linear orders with computable natural relations

We study the algorithmic complexity of natural relations on initial segments of computable linear orders. We prove that there exists a computable linear order with computable density relation such that its Π₁⁰-initial segment has no computable presentation with a computable density relation. We also prove that the same holds for a right limit and a left limit relations.     

On the number of segments needed in a piecewise linear approximation

The introduction of high-speed circuits to realize an arithmetic function f as a piecewise linear approximation has created a need to understand how the number of segments depends on the interval a≤x≤b and the desired approximation error ε. For the case of optimum non-uniform segments, we show that the number of segments is given as , (ε→0⁺), where . Experimental data shows that this approximation is close to the exact number of segments for a set of 14 benchmark functions. We also show that, if the segments have the same width (to reduce circuit complexity), then the number of segments is given by , (ε→0⁺), where .     

The Pathmox approach for PLS path modeling: Discovering which constructs differentiate segments

The problem of heterogeneity represents a very important issue in the decision‐making process. Furthermore, it has become common practice in the context of marketing research to assume that different population parameters are possible depending on sociodemographic and psycho‐demographic variables such as age, gender, and social status. In recent decades, numerous approaches have been proposed with the aim of involving heterogeneity in the parameter estimation procedures. In partial least squares path modeling, the common practice consists of achieving a global measurement of the differences arising from heterogeneity. This leaves the analyst with the important task of detecting, a posteriori, which are the causal relationships (ie, path coefficients) that produce changes in the model. This is the case in Pathmox analysis, which solves the heterogeneity problem by building a binary tree to detect those segments of population that cause the heterogeneity. In this article, we propose extending the same Pathmox methodology to asses which particular endogenous equation of the structural model and which path coefficients are responsible of the difference.     

L 2 -discrete hedging in a continuous-time model

In the setting of the Black-Scholes option pricing market model, the seller of a European option must trade continuously in time. This is, of course, unrealistic from the practical viewpoint. He must then follow a discrete trading strategy. However, it does not seem natural to hedge at deterministic times regardless of moves of the spot price. In this paper, it is supposed that the hedger trades at a fixed number N of rebalancing (stopping) times. The problem (P^N) of selecting the optimal hedging times and ratios which allow one to minimize the variance of replication error is considered. For given N rebalancing, the discrete optimal hedging strategy is identified for this criterion. The problem (P^N) is then transformed into a multidimensional optimal stopping problem with boundary constraints. The restrictive problem (P^N _BS) of selecting the optimal rebalancing for the same criterion is also considered when the ratios are given by Black-Scholes. Using the vector-valued optimal stopping theory, the existence is shown of an optimal sequence of rebalancing for each one of the problems (P^N) and (P^N _BS). It also shown BS that they are asymptotically equivalent when the number of rebalances becomes large and an optimality criterion is stated for the problem (P^N). The same study is made when more realistic restrictions are imposed on the hedging times. In the special case of two rebalances, the problem (P² _BS) is solved and the problems (P² _BS) and (P²) are transformed into two optimal stopping problems. This transformation is useful for numerical purposes.     

The Effect of Journal Writing on Achievement in and Attitudes Toward Mathematics

A teaching experiment was conducted to investigate the effect of journal writing on achievement in and attitudes toward mathematics. Achievement variables included conceptual understanding, procedural knowledge, problem solving, mathematics school achievement, and mathematical communication. Subjects were selected from first intermediate students (11–13 years) attending the International College, Beirut, Lebanon, where either English or French is the language of mathematics instruction. The journal-writing (JW) group received the same mathematics instruction as the no-journal-writing (NJW) group, except that the JW group engaged in prompted journal writing for 7 to 10 minutes at the end of each class period, three times a week, for 12 weeks. The NJW group engaged in exercises during the same period. The results of ANCOVA suggest that journal writing has a positive impact on conceptual understanding, procedural knowledge, and mathematical communication but not on problem solving, school mathematics achievement, and attitudes toward mathematics. Gender, language of instruction, mathematics achievement level, and writing achievement level failed to interact with journal writing. Student responses to a questionnaire indicated that students found journal writing to have both cognitive and affective benefits.     

Müntz-type theorem on the segments emerging from the origin

A necessary and sufficient condition is obtained for the linear span of a system of monomials {z^λ:λΛ} to be dense in the space of all continuous functions defined on the line segments emerging from the origin, where Λ is a set of nonnegative integers. The result is a generalization of the Müntz theorem to the segments emerging from the origin and an extension of the Mergelyan theorem to lacunary polynomials.     

The Utility of Interaction Analysis for Generalizing Characteristics of Science Classrooms

Validating and generalizing from holistic observation protocols of classroom practice have proven difficult. These tools miss crucial classroom characteristics, like the type of instruction, the organization of learners, and the level of cognitive engagement that occur differentially in the time span of a lesson. As a result, this study examined the potential of interaction analysis for drawing detailed inferences about science classrooms. Holistic and interaction analysis techniques were applied to an existing set of observational data from a group of high school teachers (N = 21) who were participating in long‐term professional development. Results indicate that interaction analysis provides crucial details that are otherwise absent. Questions are raised about the overall benefit and use of holistic observation protocols without supplemental information.