The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group's centroid. One recent heuristic provides an O(k3) guarantee for this objective function and an O(k2) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group's centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of O(k2) for the squared distance measure and O(k) for the distance measure.

The k-means algorithm is widely used for clustering because of its computational efficiency. Given n points in d-dimensional space and the number of desired clusters k, k-means seeks a set of k cluster centers so as to minimize the sum of the squared Euclidean distance between each point and its nearest cluster center. However, the algorithm is very sensitive to the initial selection of centers and is likely to converge to partitions that are significantly inferior to the global optimum. We present a genetic algorithm (GA) for evolving centers in the k-means algorithm that simultaneously identifies good partitions for a range of values around a specified k. The set of centers is represented using a hyper-quadtree constructed on the data. This representation is exploited in our GA to generate an initial population of good centers and to support a novel crossover operation that selectively passes good subsets of neighboring centers from parents to offspring by swapping subtrees. Experimental results indicate that our GA finds the global optimum for data sets with known optima and finds good solutions for large simulated data sets.

This paper presents a clustering algorithm for partitioning a minimum spanning tree with a constraint on minimum group size. The problem is motivated by microaggregation, a disclosure limitation technique in which similar records are aggregated into groups containing a minimum of k records. Heuristic clustering methods are needed since the minimum information loss microaggregation problem is NP-hard. Our MST partitioning algorithm for microaggregation is sufficiently efficient to be practical for large data sets and yields results that are comparable to the best available heuristic methods for microaggregation. For data that contain pronounced clustering effects, our method results in significantly lower information loss. Our algorithm is general enough to accommodate different measures of information loss and can be used for other clustering applications that have a constraint on minimum group size.

The paper presents a method for generating and displaying wireframe approximations to surfaces of constant value (or iso-surfaces). Input to the method is a data grid, a volume decomposition with each of whose vertices is associated a scalar value. During a preprocessing phase, the method constructs a threshold-independent data structure based upon the given data grid. The data structure relates the edges of an iso-surface wireframe to the edges of the data grid, for all possible threshold values. During the subsequent rendering phase, the data structure supports efficient generation and display of the iso-surface wireframe corresponding to any selected threshold value. The technique is efficient enough to form the basis for an interactive software system for visualizing iso-surfaces.

Computer graphics has long been concerned with representing and displaying surfaces in three-dimensional space. The author addresses the questions of representation and display in a higher dimensional setting, specifically, that of 3-manifolds immersed in four-dimensional space. The author describes techniques for visualizing the cross-section surfaces of a 3-manifold formed by a cutting hyperplane. The manifold is first triangulated, so that the cross-section may be computed on a per tetrahedron basis. The triangulated manifold is stored in a data structure which efficiently supports calculation of curvature. These techniques have been implemented on Personal IRIS.>

Article Free Access Share on Primitives for the manipulation of three-dimensional subdivisions Authors: D. P. Dobkin Department of Computer Science, Princeton University, Princeton, New Jersey Department of Computer Science, Princeton University, Princeton, New JerseyView Profile , M. J. Laszlo Department of Computer Science, Princeton University, Princeton, New Jersey Department of Computer Science, Princeton University, Princeton, New JerseyView Profile Authors Info & Claims SCG '87: Proceedings of the third annual symposium on Computational geometryOctober 1987 Pages 86–99https://doi.org/10.1145/41958.41967Online:01 October 1987Publication History 47citation696DownloadsMetricsTotal Citations47Total Downloads696Last 12 Months10Last 6 weeks4 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