We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in @@@@d in time 𝒪(Τd(N, N) logd N), where Τd(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in @@@@d. If Τd(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to 𝒪(Τd(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time 𝒪((nm log n log m)2/3 + m log2 n + n log2 m) in @@@@3, which yields an 𝒪(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in @@@@3.
We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo [Me1]. The expected running time of our algorithm is &Ogr;(n4/3 log 8/3 n). A deterministic version of our procedure runs in time &Ogr;(n3/2 log5/2 n). Both versions improve the previously best known upper bound of &Ogr;(n9/5 log4/5 n) by Chazelle [Ch]. A simple &Ogr;(n log n) time algorithm for computing an approximation of the median distance is also presented.
To construct a short tour through points in the plane, the points are sequenced as they appear along a spacefilling curve. This heuristic consists essentially of sorting, so it is easily coded and requires only O(N) memory and O(N log N) operations. Its performance is competitive with that of other fast methods.
We describe an antialiasing system for ray tracing based on adaptive progressive refinement. The goals of the system are to produce high quality antialiased images at a modest average sample rate, and to refine the image progressively so that the image is available in a usable form early and is refined gradually toward the final result.The method proceeds by adaptive stochastic sampling of the image plane, evaluation of the samples by ray tracing, and image reconstruction from the samples. Adaptive control of the sample generation process is driven by three basic goals: coverage of the image, location of features, and confidence in the values at a distinguished "pixel level" of resolution.A three-stage process of interpolation, filtering, and resampling is used to reconstruct a regular grid of display pixels. This reconstruction can be either batch or incremental.
Annotator is a prototype to investigate the application of AI techniques to the annotation of engineering drawings. In particular, Annotator addresses drawings of piping systems such as those for chemical plants or waste treatment facilities. The isometric representation of the piping system is selected because it is the most numerous type of drawing in plant design. Knowledge contained in hierarchies represents the CAD model of the piping system, features of the model and features of the drawing. Production rules about relationships among model items and features make annotation decisions, creating instances in a hierarchy of drawing annotations. Issues in geometry such as parallelism and perpendicularity and the translation of the 3-D model world into the 2-D drawing representation are addressed. Algorithms determine geometric intersections; rules specify whether intersections between given object classes are considered acceptable. Although Annotator prototype is separate from the CAD/CAM environment, the Annotator prototype illustrates the potential for fully automating the annotation process through representation of the knowledge about a piping model and its dimensioning requirements within a rule-based, object-oriented hierarchy.