Shape representation is a fundamental topic in geometric modeling, which is ubiquitous in computer graphics. Compared with the explicit and implicit shape representations, the medial representation possesses many advantages. It provides a comprehensive understanding of the shapes, since it gives direct access to both the boundaries and the interiors of the shapes. Although there are many medial axis computation algorithms which are able to filter noises in the medial axis, introduced by the perturbations on the boundary, and generate stable medial axis transforms of the input shapes, the medial axis transforms are usually represented in a redundant way with numerous primitives, which brings down the flexibility of the medial axis transform and hinders the popularity of the medial axis transform in geometric applications. In this thesis, we propose compact representations of the medial axis transforms for 2D and 3D shapes. The first part of this thesis proposes a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in the 3D space to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. The second part of this thesis discusses improvements on the existing medial axis computation algorithms, and represent the medial axis transform of a 3D shape in a compact way. The CVT remeshing framework is applied on an initial medial axis transform to promote the mesh quality of the medial axis. The simplified medial axis transform is then optimized by minimizing the approximation error of the shape reconstructed from the medial axis transform to the original 3D shape. Our results on various 2D and 3D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D and 3D shapes. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Not available / text

Not available / text

Not available / text

Not available / text

The use of randomized algorithms and protocols is ubiquitous in computer science. Randomized solutions are typically faster and simpler than deterministic ones for the same problem. In addition, many computational problems (for example in cryptography and distributed computing) are impossible to solve without access to randomness. In computer science, access to randomness is usually modeled as access to a string of uncorrelated uniformly random bits. Although it is widely believed that many physical phenomena are inherently unpredictable, there is a gap between the computer science model of randomness and what is actually available. It is not clear where one could find such a source of uniformly distributed bits. In practice, computers generate random bits in ad-hoc ways, with no guarantees on the quality of their distribution. One aim of this thesis is to close this gap and identify the weakest assumption on the source of randomness that would still permit the use of randomized algorithms and protocols. This is achieved by building randomness extractors ... Such an algorithm would allow us to use a compromised source of randomness to obtain truly random bits, which we could then use in our original application. Randomness extractors are interesting in their own right as combinatorial objects that look random in strong ways. They fall into the class of objects whose existence is easy to check using the probabilistic method (i.e., almost all functions are good randomness extractors), yet finding explicit examples of a single such object is non-trivial. Expander graphs, error correcting codes, hard functions, epsilon biased sets and Ramsey graphs are just a few examples of other such objects. Finding explicit examples of extractors is part of the bigger project in the area of derandomization of constructing such objects which can be used to reduce the dependence of computer science solutions on randomness. These objects are often used as basic building blocks to solve problems in computer science. The main results of this thesis are: Extractors for Independent Sources: The central model that we study is the model of independent sources. Here the only assumption we make (beyond the necessary one that the source of randomness has some entropy/unpredictability), is that the source can be broken up into two or more independent parts. We show how to deterministically extract true randomness from such sources as long as a constant (as small as 3) number of sources is available with a small amount of entropy. Extractors for Small Space Sources: In this model we assume that the source is generated by a computationally bounded processes -- a bounded width branching program or an algorithm that uses small memory. This seems like a plausible model for sources of randomness produced by a defective physical device. We build on our work on extractors for independent sources to obtain extractors for such sources. Extractors for Low Weight Affine Sources: In this model, we assume that the source gives a random point from some unknown low dimensional affine subspace with a low-weight basis. This model generalizes the well studied model of bit-fixing sources. We give new extractors for this model that have exponentially small error, a parameter that is important for an application in cryptography. The techniques that go into solving this problem are inspired by the techniques that give our extractors for independent sources. Ramsey Graphs: A Ramsey graph is a graph that has no large clique or independent set. We show how to use our extractors and many other ideas to construct new explicit Ramsey graphs that avoid cliques and independent sets of the smallest size to date. Distributed Computing with Weak Randomness: Finally, we give an application of extractors for independent sources to distributed computing. We give new protocols for Byzantine Agreement and Leader Election that work when the players involved only have access to defective sources of randomness, even in the presence of completely adversarial behavior at many players and limited adversarial behavior at every player. In fact, we show how to simulate any distributed computing protocol that assumes that each player has access to private truly random bits, with the aid of defective sources of randomness. / text

published_or_final_version / abstract / toc / Computer Science and Information Systems / Master / Master of Philosophy

published_or_final_version / Computer Science and Information Systems / Master / Master of Philosophy

published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

Thesis (PhD)--University of South Australia, 1996