Advertisement

Research and Advances

Planar point location using persistent search trees

A classical problem in computational geometry is the planar point location problem. This problem calls for preprocessing a polygonal subdivision of the plane defined by n line segments so that, given a sequence of points, the polygon containing each point can be determined quickly on-line. Several ways of solving this problem in O(log n) query time and O(n) space are known, but they are all rather complicated. We propose a simple O(log n)-query-time, O(n)-space solution, using persistent search trees. A persistent search tree differs from an ordinary search tree in that after an insertion or deletion, the old version of the tree can still be accessed. We develop a persistent form of binary search tree that supports insertions and deletions in the present and queries in the past. The time per query or update is O(log m), where m is the total number of updates, and the space needed is O(1) per update. Our planar point location algorithm is an immediate application of this data structure. The structure also provides an alternative to Chazelle's "hive graph" structure, which has a variety of applications in geometric retrieval.
Opinion

Viewpoint: Military direction of academic CS research

Most computer scientists know that the Department of Defense (DOD) supplies most of the funds for academic research, but few know how profoundly the funding situation has changed over the last decade. In 1976 most basic research in academic computer science was funded by the National Science Foundation (NSF) [see Figure 1]. In 1985 NSF's "market share" is much less than DoD's. When applied research money is added in, as in Figure 2 (on the next page), DOD'S preeminence is even more marked. Allowing $25 million for industrial, state, institutional, and other support in 1985 (exact data are unavailable), I conclude that most academic computer science (CS) research is now directed by military agencies.
Research and Advances

The human aspects of computing: a note on this collection

What makes computer users happy? Can systems help humans to use them? Does programming sharpen other thinking skills? Is computer anxiety important? Will programmers use Ada packages? How do students learn programming concepts? Are spelling correctors at their limits? When does the work load on a terminal get too heavy? Are instruction sets too large? These nine questions define some important issues for those of us who study human factors—the ways hardware and software affect, and are affected by, their users. Although the major accomplishments in the field will always rest on careful inspiration, to some degree these questions can be resolved empirically. Generally, empirical work falls into three broad categories: With experiments the goal is to determine whether some design or principle A is better than some design or principle B. Ideally, experimenters should make some tentative hypothesis first, or at least, decide what needs to be known. In data collection the objective is to observe users, give questionnaires, examine listings, count errors, or otherwise record data. By examining such data, we are able to draw conclusions and discover trouble spots. General observation is a method that involves complete systems or prototypes. These systems are observed, measured in broad ways, compared, or iteratively redesigned to complement the behavior of typical users. The goal is to understand the needs of users and to optimize system behavior. Although not at all by choice, only the first two of these categories are represented in this collection. As with most papers that are accepted and appear in print, the reviewers or editors have some special reason for liking a paper in the first place. This reason may not appear in the reviews of the paper, but it does capture some underlying point or principle deemed to be important. Each of the articles in this special section is a short description of a study addressing one of the nine questions. The results of these studies do not always reinforce conventional wisdom. Some of the conclusions are provocative. I invite you to read the articles and to see whether you agree with their conclusions.
Research and Advances

Impact of the technological environment on programmer/analyst job outcomes

Recent research has shown that key DP/IS personnel job outcomes (e.g., turnover, organizational commitment, job satisfaction) are affected by job design, leadership characteristics, and role variables. This study investigates another class of variables, the technological environment faced by DP/IS personnel, that might impact these job outcomes. The technological environment includes (1) development methodologies employed, (2) project teams and reporting relationships, and (3) work characteristics. Variables from all classes were found to impact DP/IS job outcomes. Over 11 percent of the variance in DP/IS job satisfaction is explained by these variables.
Research and Advances

Normalization of relations and PROLOG

A program for the normalization of relations that is written in Prolog has several advantages relative to programs written in conventional programming languages: notably, conciseness and clarity. The program presented here implements several normalization algorithms and is suitable for the interactive design of small database applications and as a teaching aid.
Research and Advances

Opportunities for research on numerical control machining

Numerical control (NC) machining could be reinvigorated by adapting robotic software technology. Regrettably, pressures are mounting in industry to constrain robots to NC standards, and the academic community views NC as an obsolete, solved problem, with little remaining scholarly challenge. Grossman examines the current status of APT, an NC language, and proposes the merging of APT with a modern robotics language.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More