Search
Join ACM

Software Engineering and Programming Languages

Advertisement

Research and Advances

Software development of real-time systems

Concentrating on those aspects of software development peculiar to real-time systems, this collection of development methods and tools emphasizes incremental development; the testing of tusk interfaces during integration testing, as well as unit and partial integration testing on the development system; and the development of automated tools to assist in the testing process.
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.
and
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.
and
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.
Research and Advances

TID—a translation invariant data structure for storing images

There are a number of techniques for representing pictorial information, among them are borders, arrays, and skeletons. Quadtrees are often used to store black and white picture information. A variety of techniques have been suggested for improving quadtrees, including linear quadtrees, QMATs (quadtree medial axis transform), forests of quadtrees, etc. The major purpose of these improvements is to reduce the storage required without greatly increasing the processing costs. All of these methods suffer from the fact that the structure of the underlying quadtree can be very sensitive to the placement of the origin. In this paper we discuss a translation invariant data structure (which we name TID) for storing and processing images based on the medial axis transform of the image that consists of all the maximal black squares contained in the image. We also discuss the performance of TID with other existing structures such as QMATs, forests of quadtrees, and normalized quadtrees. Some discussion on the union and intersection of images using TID is included.
and

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