Bridging the modeling and rendering gap between the existing triangle and point primitives, we explore the use of line segments as a new primitive to represent and render 3D models. Our main contribution extends the anti-aliasing theory in texture mapping to anti-aliased line segment rendering, and presents an approximation algorithm to render high quality anti-aliased opaque and transparent line segments in 3D models. This antialiasing technique is empirically validated by building a software pipeline to render models of any combination of the three types of modeling primitives: triangles, line segments and points. Our experiment shows that models comprising line segments are generally more efficient and effective for high quality rendering as compared to their corresponding pure point models.

J. Nievergelt, M. Freeston; Special Issue Editorial Spatial data: applications, concepts, techniques, The Computer Journal, Volume 37, Issue 1, 1 January 1

The design of spatial data structures has made great strides in recent years in response to be increasing importance of applications such as CAD that require great efficiency in spatial database technology and in computational geometry. The variety of spatial data structures and retrieval algorithms known suggests that it is difficult or impossible to design general purpose structures that perform well across the entire spectrum of objects to be stored and queries to be processed—generality comes at the cost of performance and increased algorithm complexity. Thus simple algorithms that perform efficiently on a restricted class of problems are clearly of interest. The guard file is a new data structure, with its access and update algorithms, designed to answer stabbing and intersection queries on a dynamic collection of spatial objects that satisfy a shape constraint. The objects stored must be ‘fat’ in a technical sense, namely convex with an aspect ratio (width/length) ≥f, where f is a constant characteristics of the class, 0

Traditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a grid partition of the search space and of a grid directory , which are the keys to a dynamic file structure called the grid file . This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.

introduction Free Access Share on Guest Editor's Introduction to Special Issue on Computational Geometry Author: Jurg Nievergelt View Profile Authors Info & Claims ACM Transactions on GraphicsVolume 3Issue 4pp 241–243https://doi.org/10.1145/357346.357347Published:01 October 1984Publication History 2citation393DownloadsMetricsTotal Citations2Total Downloads393Last 12 Months21Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A simple model of a system of processors competing for resources is presented. It permits the derivation of upper bounds for the utilization of the system components that are surprisingly close to those previously obtained from far more complicated analyses or simulations.

Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.

This paper discusses an automatic tutor of programming, implemented on the PLATO IV CAI system [1] as a part of an automated instructional system for computer science being developed at the University of Illinois [8]. This tutor exposes the introductory student to structured programming concepts and top-down problem solution techniques by means of example. The student develops (on-line, using an approach based on stepwise refinement [11]) a solution to a single, relatively complex programming problem (symbolic differentiation of a polynomial). Student and tutor engage in an interactive dialogue during this problem-solving process, the tutor providing hints regarding solution steps, and comments about program structure and efficiency. A small sample of the types of responses the tutor might make is presented

A steadily increasing fraction of human activities involves interacting with machines, and this interaction will become more sophisticated as more and more machines in our environment are controlled by computers. As the degree of sophistication of this interaction increases, its quality becomes more important. This is particularly true in computer-based education where a student is expected to learn something by interacting with a machine for an extended period of time.

A code of integers into binary sequences is called a difference-preserving code (DP code) if it has the following two properties: 1) if the absolute value of the difference between two integers is less than or equal to a certain threshold, the Hamming distance between their codewords is equal to this value and 2) if the absolute value of the difference between two integers exceeds the threshold, then the Hamming distance between their codewords also exceeds this threshold. Such codes (or slight modifications thereof) have also been called path codes, circuit codes, or snake-in-the-box codes. This paper discusses the application of DP codes to pattern recognition and classification problems and presents a construction of efficient DP codes whose information content is asymptotically (in the length of codewords) of the order of theoretical upper bounds.

This paper describes a project we have recently started for automating introductory computer science courses. Why should these courses be automated? At the University of Illinois there are currently about 2000 students per semester taking various introductory programming courses: engineers, social scientists, teachers, physical scientists, computer science majors, etc., each group having its own particular needs. These courses are taught in sections of about 100 students each, with an additional hour of discussion in groups of about 20 students. In our experience it is very difficult to organize these courses in such a way that students both learn something and are happy with the material presented. The main difficulty seems to come from the fact that a beginning programmer needs a lot of individual help, and this cannot be provided in large sections. We are now convinced that these courses cannot be improved within the current setup, and since enrollments in these courses are increasing, the situation is bound to grow worse unless something new is tried. We assume that the situation we have described is typical of many large universities.

Two upper bounds for the total path length of binary trees are obtained. One is for node-trees, and bounds the internal (or root-to-node) path length; the other is for leaf-trees, and bounds the external (or root-to-leaf) path length. These bounds involve a quantity called the balance, which allows the bounds to adapt from the n log n behavior of a completely balanced tree to the n 2 behavior of a most skewed tree. These bounds are illustrated for the case of Fibonacci trees.

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is only moderately longer than in completely balanced trees. Trees of bounded balance differ from other classes of binary search trees in that they contain a parameter which can be varied so the compromise between short search time and infrequent restructuring can be chosen arbitrarily.

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is only moderately longer than in completely balanced trees. Trees of bounded balance differ from other classes of binary search trees in that they contain a parameter which can be varied so the compromise between short search time and infrequent restructuring can be chosen arbitrarily.

A new technique for directing the flow of control in block structured programs is described. It allows a programmer to delay using the outcome of a test indefinitely, and to make the entry and exit of begin-end blocks conditional upon the last test performed. It was designed as a low-level technique in terms of which all the block structure control statements common in high-level programming languages can be implemented easily and efficiently. This technique is the main tool for directing the flow of control in the programming language NUCLEOL, and is considered to be particularly useful for program debugging.

The proof of the unsolvability of the halting problem can be reformulated to show that, in general, the best one can do to estimate the run time of programs is to execute them.

In this note the problem is considered whether or not selfmodifying programs are in principle more powerful than fixed, i.e., nonselfmodifying ones.