Although mature technologies exist for acquiring images, geometry, and normals of small objects, they remain cumbersome and time-consuming for non-experts to employ on a large scale. In an archaeological setting, a practical acquisition system for routine use on every artifact and fragment would open new possibilities for archiving, analysis, and dissemination. We present an inexpensive system for acquiring all three types of information, and associated metadata, for small objects such as fragments of wall paintings. The acquisition system requires minimal supervision, so that a single, non-expert user can scan at least 10 fragments per hour. To achieve this performance, we introduce new algorithms to robustly and automatically align range scans, register 2-D scans to 3-D geometry, and compute normals from 2-D scans. As an illustrative application, we present a novel 3-D matching algorithm that efficiently searches for matching fragments using the scanned geometry.

In this paper, we investigate a data-driven synthesis approach to constructing 3D geometric surface models. We provide methods with which a user can search a large database of 3D meshes to find parts of interest, cut the desired parts out of the meshes with intelligent scissoring, and composite them together in different ways to form new objects. The main benefit of this approach is that it is both easy to learn and able to produce highly detailed geometric models -- the conceptual design for new models comes from the user, while the geometric details come from examples in the database. The focus of the paper is on the main research issues motivated by the proposed approach: (1) interactive segmentation of 3D surfaces, (2) shape-based search to find 3D models with parts matching a query, and (3) composition of parts to form new models. We provide new research contributions on all three topics and incorporate them into a prototype modeling system. Experience with our prototype system indicates that it allows untrained users to create interesting and detailed 3D models.

As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this article, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a Web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46 to 245% better performance than related shape-matching methods during precision--recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).

Measuring the similarity between 3D shapes is a fundamental problem, with applications in computer graphics, computer vision, molecular biology, and a variety of other fields. A challenging aspect of this problem is to find a suitable shape signature that can be constructed and compared quickly, while still discriminating between similar and dissimilar shapes.In this paper, we propose and analyze a method for computing shape signatures for arbitrary (possibly degenerate) 3D polygonal models. The key idea is to represent the signature of an object as a shape distribution sampled from a shape function measuring global geometric properties of an object. The primary motivation for this approach is to reduce the shape matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence, or model fitting.We find that the dissimilarities between sampled distributions of simple shape functions (e.g., the distance between two random points on a surface) provide a robust method for discriminating between classes of objects (e.g., cars versus airplanes) in a moderately sized database, despite the presence of arbitrary translations, rotations, scales, mirrors, tessellations, simplifications, and model degeneracies. They can be evaluated quickly, and thus the proposed method could be applied as a pre-classifier in a complete shape-based retrieval or analysis system concerned with finding similar whole objects. The paper describes our early experiences using shape distributions for object classification and for interactive web-based retrieval of 3D models.

This paper addresses the problem of lossy compression of arrangements. Given an arrangement of $n$ lines in the plane, we show how to construct another arrangement consisting of many fewer lines. We give theoretical and empirical bounds to demonstrate the tradeoffs between the size of the new arrangement and the error from lossiness.

In this video we illustrate a technique for lossy compression of arran gements. The video also demonstrates the visualization techniques that facilitated the research. Detailed description of the algorithm appears in the full paper in this proceedings~\cite{DT-01}.

Measuring the similarity between 3D shapes is a fundamental problem, with applications in computer vision, molecular biology, computer graphics, and a variety of other fields. A challenging aspect of this problem is to find a suitable shape signature that can be constructed and compared quickly, while still discriminating between similar and dissimilar shapes. In this paper, we propose and analyze a method for computing shape signatures for arbitrary (possibly degenerate) 3D polygonal models. The key idea is to represent the signature of an object as a shape distribution sampled from a shape function measuring the global geometric properties of an object. The primary motivation for this approach is to reduce the shape matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence or model fitting. We find that the dissimilarities between sampled distributions of simple shape functions (e.g. the distance between two random points on a surface) provide a robust method for discriminating between classes of objects (e.g. cars versus airplanes) in a moderately sized database, despite the presence of arbitrary translations, rotations, scales, reflections, tessellations, simplifications and model degeneracies. They can be evaluated quickly, and thus the proposed method could be applied as a pre-classifier in an object recognition system or in an interactive content-based retrieval application.

No abstract available.

We present a new method for user controlled morphing of two \nhomeomorphic triangle meshes of arbitrary topology. In particular we focus on the problem of establishing a correspondence map between source and target meshes. Our method employs the MAPS algorithm to parameterize both meshes over simple base domains and an additional harmonic map bringing the latter into correspondence. \nTo control the mapping the user specifies any number of \nfeature pairs, which control the parameterizations produced by the MAPS algorithm. Additional controls are provided through a direct manipulation interface allowing the user to tune the mapping between the base domains. We give several examples of æsthetically pleasing morphs which can be created in this manner with little user input. Additionally we demonstrate examples of temporal \nand spatial control over the morph.

No abstract available.

No abstract available.

An irregular connectivity mesh representative of a surface having an arbitrary topology is processed to generate a parameterization which maps points in a coarse base domain to points in the mesh. An illustrative embodiment uses a multi-level mesh simplification process in conjunction with conformal mapping to efficiently construct a parameterization of a mesh comprising a large number of triangles over a base domain comprising a smaller number of triangles. The parameterization in this embodiment corresponds to the inverse of function mapping each point in the original mesh to one of the triangles of the base domain, such that the original mesh can be reconstructed from the base domain and the parameterization. The mapping function is generated as a combination of a number of sub-functions, each of which relates data points in a mesh of one level in a simplification hierarchy to data points in a mesh of the next coarser level of the simplification hierarchy. The parameterization can also be used to construct, from the original irregular connectivity mesh, an adaptive remesh having a regular connectivity which is substantially easier to process than the original mesh.

Although routing is a well-studied problem in various contexts, there remain unsolved problems in routing edges for graph layouts. In contrast with techniques from other domains such as VLSI CAD and robotics, where physical constraints play a major role, aesthetics play the more important role in graph layout. For graphs, we seek paths that are easy to follow and add meaning to the layout. We describe a collection of aesthetic attributes applicable to drawing edges in graphs, and present a general approach for routing individual edges subject to these principles. We also give implementation details and survey difficulties that arise in an implementation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Patterns used for supersampling in graphics have been analyzed from statistical and signal-processing viewpoints. We present an analysis based on a type of isotropic discrepancy—how good patterns are at estimating the area in a region of defined type. We present algorithms for computing discrepancy relative to regions that are defined by rectangles, halfplanes, and higher-dimensional figures. Experimental evidence shows that popular supersampling patterns have discrepancies with better asymptotic behavior than random sampling, which is not inconsistent with theoretical bounds on discrepancy.

The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory. computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating-point arithmetic, this assumption can lead to serous errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of “thick” facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.

We present a general approach to solving the minimizing disagreement problem for geometric hypotheses with finite VC-dimension.

Article Free Access Share on Strategies for polyhedral surface decomposition: an experimental study Authors: Bernard Chazelle Department of Computer Science, Princeton University Department of Computer Science, Princeton UniversityView Profile , David P. Dobkin Department of Computer Science, Princeton University Department of Computer Science, Princeton UniversityView Profile , Nadia Shouraboura Program in Applied and Computer. Math., Princeton University Program in Applied and Computer. Math., Princeton UniversityView Profile , Ayellet Tal Department of Computer Science, Princeton University Department of Computer Science, Princeton UniversityView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 297–305https://doi.org/10.1145/220279.220311Online:01 September 1995Publication History 25citation451DownloadsMetricsTotal Citations25Total Downloads451Last 12 Months4Last 6 weeks2 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

No abstract available.

Investigates the visualization of geometric algorithms. We discuss how limiting the domain makes it possible to create a system that enables others to use it easily. Knowledge about the domain can be very helpful in building a system which automates large parts of the user's task. A system can be designed to isolate the user from any concern about how graphics is done. The application need only specify "what" happens and need not be concerned with "how" to make it happen on the screen. We develop a conceptual model and a framework for experimenting with it. We also present a system, GASP (Geometric Animation System, Princeton), which implements this model. GASP allows quick generation of 3D geometric algorithm visualizations, even for highly complex algorithms. It also provides a visual debugging facility for geometric computing. We show the utility of GASP by presenting a variety of examples.>

No abstract available.

No abstract available.

This paper describes a system, GASP, that facilitates the visualization of geometric algorithms. The user need not have any knowledge of computer graphics in order to quickly generate a visualization. The system is also intended to facilitate the task of implementing and debugging geometric algorithms. The viewer is provided with a comfortable user interface enhancing the exploration of an algorithm's functionality. We describe the underlying concepts of the system as well as a variety of examples which illustrate its use.>

We develop algorithms for computing the discrepancy of point sets in various Euclidean range spaces.

No abstract available.

We show how to triangulate polygonal regions---adding extra vertices as necessary--- with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle in a triangulation of an n-vertex polygon (with holes) is a constant fraction of the largest possible. For simple polygons, using O(n log n) triangles, we can guarantee that the largest angle is no greater than 150 ffi . This bound increases to O(n 3=2 ) triangles for the case of polygons with holes. We can add the guarantee on smallest height to these no-large-angle results, without increasing the asymptotic complexity of the triangulation. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n 1:85 ) triangles. Keywords: Computational geometry, mesh generation, triangulation, angle condition. 1. Introduction There have been a number of recent papers on the general problem of triangulating a planar point set or pol...

The interaction between computer graphics and computational geometry is explored through two scenarios. Spatial subdivisions studied from the viewpoint of computational geometry are shown to have found application in computer graphics. Hidden surface removal problems of computer graphics have led to sweep-line and area subdivision algorithms in computational geometry. Two promising research area with practical applications, precise computation and polyhedral decomposition, are examined.>

Let S be a set, f : S × S → R + a bivariate function, and f ( x , S ) the maximum value of f ( x , y ) over all elements y ∈ S . We say that f is decomposable with respect with the maximum if f ( x , S ) = max { f ( x , S 1 ), f ( x , S 2 ),…, f ( x , S k )} for any decomposition S = ∪ i =1 i = k S i . Computing the maximum (minimum) value of a decomposable function is inherent in many problems of computational geometry and robotics. In this paper, a general technique is presented for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S . Our result holds for a semi-online model of dynamization: When an element is inserted, we are told how long it will stay. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) retangles determined by a set of points. These problems are fundamental to application areas such as robotics, VLSI masking, and optimization.

No abstract available.

Methods of rendering reflections in curved surfaces are examined. A numerical algorithm to derive spherical reflections is presented. This algorithm has many attractive qualities, such as low computation costs, object space coherence, device and resolution independence, and generation of maximum information about reflections in curved surfaces. The authors demonstrate that rendering reflections is a difficult problem, as it defies analytic solutions. The authors indicate several alternatives for generalizing this method to a broader domain.>

We present a method for tracing a curve that is represented as the contour of a function in Euclidean space of any dimension. The method proceeds locally by following the intersections of the contour with the facets of a triangulation of space. The algorithm does not fail in the presence of high curvature of the contour; it accumulates essentially no round-off error and has a well-defined integer test for detecting a loop. In developing the algorithm, we explore the nature of a particular class of triangulations of Euclidean space, namely, those generated by reflections.

The authors present a general technique for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) rectangles determined by a set of points. The main appeal of the approach lies in its generality. Several research directions suggested by the work are noted.>

It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\alpha + m)$, where $\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time.

A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r > 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.

Geometric computations, like all numerical procedures, are extremely prone to roundoff error. However, virtually none of the numerical analysis literature directly applies to geometric calculations. Even for line intersection, the most basic geometric operation, there is no robust and efficient algorithm. Compounding the difficulties, many geometric algorithms perform iterations of calculations reusing previously computed data. In this paper, we explore some of the main issues in geometric computations and the methods that have been proposed to handle roundoff errors. In particular, we focus on one method and apply it to a general iterative intersection problem. Our initial results seem promising and will hopefully lead to robust solutions for more complex problems of computational geometry.

We consider the problem of converting boundary representations of polyhedral objects into constructive-solid-geometry (CSG) representations. The CSG representations for a polyhedron P are based on the half-spaces supporting the faces of P. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practical O(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We also prove that such nice formulæ do not always exist for general polyhedra in three dimensions.

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

Let S be any set of N points in the plane and let DT(S) be the graph of the Delaunay triangulation of S. For all points a and b of S, let d(a, b) be the Euclidean distance from a to b and let DT(a, b) be the length of the shortest path in DT(S) from a to b. We show that there is a constant c(≤ 1+√5/2 π ≈ 5.08) independent of S and N such that DT(a, b)/d(a, b) ≪ c.

One of the basic geometric operations involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation in which the objects are given as input and their intersection is returned as output. For many applications, however, it may be assumed that the objects already exist within the computer and that the only output desired is a single piece of data giving a common point if the objects intersect or reporting no intersection if they are disjoint. For this problem, none of the previous lower bounds are valid and algorithms are proposed requiring sublinear time for their solution in two and three dimensions.

Article Probing convex polytopes Share on Authors: D Dobkin Department of Computer Science, Princeton University, Princeton, New Jersey Department of Computer Science, Princeton University, Princeton, New JerseyView Profile , H Edelsbrunner Amoco Foundation Faculty Development in Computer Science, Department of Computer Science, University of Illinois, Urbana-Champaign, Illinois Amoco Foundation Faculty Development in Computer Science, Department of Computer Science, University of Illinois, Urbana-Champaign, IllinoisView Profile , C K Yap Courant Institute of Mathematical Sciences, New York University, New York, New York Courant Institute of Mathematical Sciences, New York University, New York, New YorkView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 424–432https://doi.org/10.1145/12130.12174Online:01 November 1986Publication History 44citation304DownloadsMetricsTotal Citations44Total Downloads304Last 12 Months3Last 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 SiteGet Access

Given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time $O(kn\lg n + n\lg ^2 n)$. For the special case $k = 3$ we give $O(n\lg n)$ algorithms for these problems. Several related issues are discussed.

Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, plaraes, and polyhedra in three dimensions.

Distributed systems make possible both a high degree of concurrency and robustness in the face of failure. One approach to achieving these goals is to employ pools of servers implementing major system functions. This paper describes the concept of pools of servers, and presents logically distributed, robust algorithms for one problem arising in this approach: the allocation of servers to clients. Three types of allocation problems are identified: free servers, preferred servers, and retentive servers. Allocation protocols based upon the idea of hash addressing are described and analyzed.

Given n points in the plane, we present algorithms for finding maximum perimeter or area convex k-gons with vertices k of the given n points. Our algorithms work in linear space and time O(knlg n + n lg 2n). For the special case k = 3 we give O (nlgn) algorithms for these problems. Several related issues are discussed.

Algorithms for findmg medians and solving arbitrary selection problems using a minimum number of data storage locations are investigated A linear-tmle algorithm is given in the first case, and it ~s shown that no such scheme exists for many other interesting selection problems, such as finding a quartile A right trade-off is demonstrated balancing extra space versus time.

A failing of existing data structures for maintaining balanced trees is their inability to remember the situation they held at previous times. We propose a structure from which it is possible to efficiently reconstruct the state of the data it represented at any time. Applications of this data structure to a number of important problems in geometric computation are also given.

Perhaps the most important application of computer geometry involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation where the objects are given as input and their intersection is returned as output. However, for many applications, we may assume that the objects already exist within the computer and that the only output desired is a single piece of data giving a common point if the objects intersect or reporting no intersection if they are disjoint. For this problem, none of the previous lower bounds are valid and we propose algorithms requiring sublinear time for their solution in 2 and 3 dimensions.

Addition chains are considered for specific polynomials. It is shown that for a wide class of polynomials the evaluation of their first n terms requires at least $n + O(n^{2/3} )$ additions. Included in this class are the first n squares, the first n cubes, $ \cdots $, the first nkth powers. The results are established by making contact with results in combinatorics.

We prove an asymptotic lower bound of 3.52n nonscalar multiplications for (degree n – 1 by degree n – 1) polynomial multiplication in a model which allows only integers as scalars. Index Terms-Algebraic complexity, lower bound, polynomial multiplication.

Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.

A common operation in geometric computing is the decomposition of complex structures into more basic structures. Since it is easier to apply most algorithms to triangles or arbitrary convex polygons, there is considerable interest in finding fast algorithms for such decompositions. We consider the problem of decomposing a simple (non-convex) polygon into the union of a minimal number of convex polygons. Although the structure of the problem led to the conjecture that it was NP-complete, we have been able to reach polynomial time bounded algorithms for exact solution as well as low degree polynomial time bounded algorithm/or approximation methods.

Users may be able to compromise databases by asking a series of questions and then inferring new information from the answers. The complexity of protecting a database against this technique is discussed here.

Computer security has been an important issue since the first computer was developed. However, with the advent of faster and more accessible machines used by many users and large quantities of shared data, this issue has achieved far greater importance. It is no longer sufficient to rely on a system of password control through which a user is protected by having a 7-letter code known only to himself, since while this may, in the best case, prevent other users from directly accessing the users area, it does little to prevent indirect access. The potential dangers from such indirect access increase manyfold. In this survey, we shall discuss protection in three forms. The first is the privacy-certification problem for digital information. To maintain the privacy and authenticity of information cryptosystems and digitalized "signature" algorithms have been devised. The second involves the problems of unauthorized users gaining access to restricted data. In this case, it is necessary to discuss access control mechanisms that can be brought to bear in order to protect each users security. A third and far more subtle method of compromising a system is through what is called "statistical inference". Here, the user obtains information that is available to him legally and uses this information to infer information to which he has no access privileges. As more secure access-control mechanisms are proposed to guard from illegal access to protected data, it is this problem which looms as the major important problem of data security. And, this problem can never be totally solved since we must grant to authorized users access to data of this type. As an illustration of this problem, consider a problem faced by the census bureau ( or any other creator of administrative databases). In such a database, sensitive information is collected about a group of individuals while guaranteeing each individual that data collected about him will not be made available to users at large. However, in order to do research on large segments of the population, it is necessary for aggregated forms of this data to be made available to certain users. Suppose that a sociologist wishes to study correlations among a population with respect to various characteristics. Then, it might be necessary to give this sociologist access to the data. However, in order to guarantee each individual's privacy, we will wish to do this in a statistical manner. That is, we will refuse to answer questions about an individual or small set of individuals, but will make available information about larger segments of society in a manner that does not give information about any individual. And the problem arises as to how to insure that no malicious user can use this information in order to determine the characteristics of a single individual. A common method that has been proposed is to refuse access to information about any set of individuals which consists of too few people and in this manner restrict access to individual data. When data is given about a set of individuals, it will then be given in an aggregated form consisting of mean or median characteristics or counts of the number of people having a certain characteristic. However, as shown below, such a limitation is often not sufficient to guarantee individual privacy. Furthermore, refusing to answer a question often gives as much information as an aggregated answer since one might be able to infer information from the reason for a non-answer. Another area where this problem is of great significance is in the problem of medical record-keeping. Here, we may wish to track a set of people having a certain ailment in their early life (or people who have been exposed to certain phenomena) in order to determine long range effects of medications or exposures. In so doing, we want to make the data as helpful as possible to medical researchers while guaranteeing individual privacy. Because of the nature of such data, it is of great value to malicious users.

Previous article Full AccessErrata: On the Number of Multiplications Required for Matrix MultiplicationR. W. Brockett and D. DobkinR. W. BrockettSearch for more papers by this author and D. DobkinSearch for more papers by this authorhttps://doi.org/10.1137/0207021PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Errata: On the Number of Multiplications Required for Matrix Multiplication." SIAM Journal on Computing, 7(2), p. 238 Previous article FiguresRelatedReferencesCited ByDetails Volume 7, Issue 2| 1978SIAM Journal on Computing History Submitted:24 August 1977Published online:31 July 2006 Article & Publication DataArticle DOI:10.1137/0207021Article page range:pp. 238-238ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

Users can compromise data bases by asking a series of questions, even when the data bases are allowed to lie.

In this paper we give a new algorithm for matrix multiplication which for n large uses $n^2 + o(n^2 )$ multiplications to multiply $n \times p$ matrices by $p \times n$ matrices provided $p \leqq \log _2 n$. Multiplication and division by 2 is necessary in this algorithm. This is to be compared with $pn^2 $ for the standard algorithm and $ \simeq p^{.58} n^2 + o(n^2 )$ for an algorithm of Hopcroft and Kerr [1] which, however, requires no multiplication and division by 2.

Classic binary search is extended to multidimensional search problems. This extension yields efficient algorithms for a number of tasks such as a secondary searching problem of Knuth, region location in planar graphs, and speech recognition.

The difficulty of evaluating integers and polynomials has been studied in various frameworks ranging from the addition-chain approach [5] to integer evaluation to recent efforts aimed at generating polynomials that are hard to evaluate [2,8,10]. Here we consider the classes of integers and polynomials that can be evaluated within given complexity bounds and prove the existence of proper hierarchies of complexity classes. The framework in which our problems are cast is general enough to allow any finite set of binary operations rather than just addition, subtraction, multiplication, and division. The motivation for studying complexity classes rather than specific integers or polynomials is analogous to why complexity classes are studied in automata-based complexity: (i) the immense difficulty associated with computing the complexity of a specific integer or polynomial; (ii) the important insight obtained from discovering the structure of the complexity classes.

Classic binary search is extended to multidimensional search problems. These new search methods can efficiently solve several important problems of computer science. Applications of these results to an open problem in the theory of computation are discussed yielding new insight into the Lba problem.

Although general theories are beginning to emerge in the area of automata based complexity theory, there are very few general methods or even general problem formulations in the area of arithmetic complexity. In this paper we propose and defend a general model for studying bilinear multiplication in order to provide a common framework for discussing a wide class of problems.