We present a convex hull algorithm that is accelerated on commodity graphics
hardware. We analyze and identify the hurdles of writing a recursive divide and
conquer algorithm on the GPU and divise a framework for representing this class
of problems. Our framework transforms the recursive splitting step into a
permutation step that is well-suited for graphics hardware. Our convex hull
algorithm of choice is Quickhull. Our parallel Quickhull implementation (for
both 2D and 3D cases) achieves an order of magnitude speedup over standard
computational geometry libraries.

We consider the problem of computing the Euler characteristic of an abstract
simplicial complex given by its vertices and facets. We show that this problem
is #P-complete and present two new practical algorithms for computing Euler
characteristic. The two new algorithms are derived using combinatorial
commutative algebra and we also give a second description of them that requires
no algebra. We present experiments showing that the two new algorithms can be
implemented to be faster than previous Euler characteristic implementations by
a large margin.

In this paper we present several results on the expected complexity of a
convex hull of $n$ points chosen uniformly and independently from a convex
shape.

(i) We show that the expected number of vertices of the convex hull of $n$
points, chosen uniformly and independently from a disk is $O(n^{1/3})$, and
$O(k \log{n})$ for the case a convex polygon with $k$ sides. Those results are
well known (see \cite{rs-udkhv-63,r-slcdn-70,ps-cgi-85}), but we believe that
the elementary proof given here are simpler and more intuitive.

We describe algorithms for finding harmonic cochains, an essential ingredient
for solving elliptic partial differential equations in exterior calculus.
Harmonic cochains are also useful in computational topology and computer
graphics. We focus on finding harmonic cochains cohomologous to a given
cocycle. Amongst other things, this allows localization near topological
features of interest. We derive a weighted least squares method by proving a
discrete Hodge-deRham theorem on the isomorphism between the space of harmonic
cochains and cohomology.

Divide and Conquer is a well known algorithmic procedure for solving many
kinds of problem. In this procedure, the problem is partitioned into two parts
until the problem is trivially solvable. Finding the distance of the closest
pair is an interesting topic in computer science. With divide and conquer
algorithm we can solve closest pair problem. Here also the problem is
partitioned into two parts until the problem is trivially solvable. But it is
theoretically and practically observed that sometimes partitioning the problem
space into more than two parts can give better performances.

Hilbert's two-dimensional space-filling curve is appreciated for its good
locality properties for many applications. However, it is not clear what is the
best way to generalize this curve to filling higher-dimensional spaces. We
argue that the properties that make Hilbert's curve unique in two dimensions,
are shared by 10694807 structurally different space-filling curves in three
dimensions. These include several curves that have, in some sense, better
locality properties than any generalized Hilbert curve that has been considered
in the literature before.

Half-space depth (also called Tukey depth or location depth) is one of the
most commonly studied data depth measures because it possesses many desirable
properties for data depth functions. The data depth contours bound regions of
increasing depth. For the sample case, there are two competing definitions of
contours: the rank-based contours and the cover-based contours.

We show that several problems of compacting orthogonal graph drawings to use
the minimum number of rows or the minimum possible area cannot be approximated
to within better than a polynomial factor in polynomial time unless P = NP.
However, there is a fixed-parameter-tractable algorithm for testing whether a
drawing can be compacted to a given number of rows.

A balanced V-shape is a polygonal region in the plane contained in the union
of two crossing equal-width strips. It is delimited by two pairs of parallel
rays that emanate from two points x, y, are contained in the strip boundaries,
and are mirror-symmetric with respect to the line xy. The width of a balanced
V-shape is the width of the strips. We first present an O(n^2 log n) time
algorithm to compute, given a set of n points P, a minimum-width balanced
V-shape covering P.

An efficient algorithm for computing the branching structure of a compact
Riemann surface defined via an algebraic curve is presented. Generators of the
fundamental group of the base of the ramified covering punctured at the
discriminant points of the curve are constructed via a minimal spanning tree of
the discriminant points. This leads to paths of minimal length between the
points, which is important for a later stage where these paths are used as
integration contours to compute periods of the surface.

We study the problem of discrete geometric packing. Here, given weighted
regions (say in the plane) and points (with capacities), one has to pick a
maximum weight subset of the regions such that no point is covered more than
its capacity. We provide a general framework and an algorithm for approximating
the optimal solution for packing in hypergraphs arising out of such geometric
settings. Using this framework we get a flotilla of results on this problem
(and also on its dual, where one wants to pick a maximum weight subset of the
points when the regions have capacities).

Given $n$ points in a circular region $C$ in the plane, we study the problems
of moving the $n$ points to its boundary to form a regular $n$-gon such that
the maximum (min-max) or the sum (min-sum) of the Euclidean distances traveled
by the points is minimized. The problems have applications, e.g., in mobile
sensor barrier coverage of wireless sensor networks. The min-max problem
further has two versions: the decision version and optimization version.

It is shown that there are examples of distinct polyhedra, each with a
Hamiltonian path of edges, which when cut, unfolds the surfaces to a common
net. In particular, it is established for infinite classes of triples of
tetrahedra.

In this paper, we consider the problem of choosing disks (that we can think
of as corresponding to wireless sensors) so that given a set of input points in
the plane, there exists no path between any pair of these points that is not
intercepted by some disk. We try to achieve this separation using a minimum
number of a given set of unit disks. We show that a logarithmic approximation
to this problem can be found in polynomial time using a greedy algorithm. To
the best of our knowledge we are the first to study this optimization problem.

There is a high demand of space-efficient algorithms in built-in or embedded
softwares. In this paper, we consider the problem of designing space-efficient
algorithms for computing the maximum area empty rectangle (MER) among a set of
points inside a rectangular region $\cal R$ in 2D. We first propose an inplace
algorithm for computing the priority search tree with a set of $n$ points in
$\cal R$ using $O(\log n)$ extra bit space in $O(n\log n)$ time. It supports
all the standard queries on priority search tree in $O(\log^2n)$ time.

The presented article contains a 3D mesh generation routine optimized with
the Metropolis algorithm. The procedure enables to produce meshes of a
prescribed volume V_0 of elements. The finite volume meshes are used with the
Finite Element approach. The FEM analysis enables to deal with a set of coupled
nonlinear differential equations that describes the electrodiffusional problem.
Mesh quality and accuracy of FEM solutions are also examined.

This document reviews the definition of the kernel distance, providing a
gentle introduction tailored to a reader with background in theoretical
computer science, but limited exposure to technology more common to machine
learning, functional analysis and geometric measure theory. The key aspect of
the kernel distance developed here is its interpretation as an L_2 distance
between probability measures or various shapes (e.g. point sets, curves,
surfaces) embedded in a vector space (specifically an RKHS).

Given a convex region in the plane, and a sweep-line as a tool, what is best
way to reduce the region to a single point by a sequence of sweeps? The problem
of sweeping points by orthogonal sweeps was first studied in [2]. Here we
consider the following \emph{slanted} variant of sweeping recently introduced
in [1]: In a single sweep, the sweep-line is placed at a start position
somewhere in the plane, then moved continuously according to a sweep vector
$\vec v$ (not necessarily orthogonal to the sweep-line) to another parallel end
position, and then lifted from the plane.

This paper considers the problem of finding a quickest path between two
points in the Euclidean plane in the presence of a transportation network. A
transportation network consists of a planar network where each road (edge) has
an individual speed. A traveller may enter and exit the network at any point on
the roads. Along any road the traveller moves with a fixed speed depending on
the road, and outside the network the traveller moves at unit speed in any
direction.

We present an algorithm to find an {\it Euclidean Shortest Path} from a
source vertex $s$ to a sink vertex $t$ in the presence of obstacles in $\Re^2$.
Our algorithm takes $O(T+m(\lg{m})(\lg{n}))$ time and $O(n)$ space. Here,
$O(T)$ is the time to triangulate the polygonal region, $m$ is the number of
obstacles, and $n$ is the number of vertices. This bound is close to the known
lower bound of $O(n+m\lg{m})$ time and $O(n)$ space. Our approach involve
progressing shortest path wavefront as in continuous Dijkstra-type method, and
confining its expansion to regions of interest.

We investigate the problem of finding reverse nearest neighbors efficiently.
Although provably good solutions exist for this problem in low or fixed
dimensions, to this date the methods proposed in high dimensions are mostly
heuristic.

Maxwell's condition states that the edges of a graph are independent in its
$k$ dimensional generic rigidity matroid only if the number of edges does not
exceed $k|V| - {k+1\choose 2}$; and this is true of every induced subgraph. We
call such graphs $G$ {\em Maxwell-independent} in $k$ dimensions. We answer the
following questions in the affirmative for the case of rigidity matroids in 3
dimensions. The questions were posed at the 2008 rigidity workshop at BIRS.

{\em Question 1:} Does {\it every} maximal, Maxwell-independent set of a
graph have size at least the rank?

Segmentation is often an essential intermediate step in image analysis. A
volume segmentation characterizes the underlying volume image in terms of
geometric information--segments, faces between segments, curves in which
several faces meet--as well as a topology on these objects. Existing algorithms
encode this information in designated data structures, but require that these
data structures fit entirely in Random Access Memory (RAM). Today, 3D images
with several billion voxels are acquired, e.g.

Given any convex $n$-gon, in this article, we: (i) prove that its vertices
can form at most $n^2/2 + \Theta(n\log n)$ isosceles trianges with two sides of
unit length and show that this bound is optimal in the first order, (ii)
conjecture that its vertices can form at most $3n^2/4 + o(n^2)$ isosceles
triangles and prove this conjecture for a special group of convex $n$-gons,
(iii) prove that its vertices can form at most $\lfloor n/k \rfloor$ regular
$k$-gons for any integer $k\ge 4$ and that this bound is optimal, and (iv)
provide a short proof that the sum of all the distances between its

In this paper, we study the following problem of reconstructing a simple
polygon: Given a cyclically ordered vertex sequence of an unknown simple
polygon P of n vertices and, for each vertex v of P, the sequence of angles
defined by all the visible vertices of v in P, reconstruct the polygon P (up to
similarity). An O(n^3 log n) time algorithm has been proposed for this problem.
We present an improved algorithm with running time O(n^2), based on new
observations on the geometric structures of the problem.

Completing Aronov et al.'s study on zero-discrepancy matrices for digital
halftoning, we determine all (m, n, k, l) for which it is possible to put mn
consecutive integers on an m-by-n board (with wrap-around) so that each k-by-l
region holds the same sum. For one of the cases where this is impossible, we
give a heuristic method to find a matrix with small discrepancy.

We study the classic graph drawing problem of drawing a planar graph using
straight-line edges with a prescribed convex polygon as the outer face. Unlike
previous algorithms for this problem, which may produce drawings with
exponential area, our method produces drawings with polynomial area. In
addition, we allow for collinear points on the boundary, provided such vertices
do not create overlapping edges.

A drawing of a given (abstract) tree that is a minimum spanning tree of the
vertex set is considered aesthetically pleasing. However, such a drawing can
only exist if the tree has maximum degree at most 6. What can be said for trees
of higher degree? We approach this question by supposing that a partition or
covering of the tree by subtrees of bounded degree is given. Then we show that
if the partition or covering satisfies some natural properties, then there is a
drawing of the entire tree such that each of the given subtrees is drawn as a
minimum spanning tree of its vertex set.

We describe computer algorithms that produce the complete set of isohedral
tilings by n-omino or n-iamond tiles in which the tiles are fundamental domains
and the tilings have 3-, 4-, or 6-fold rotational symmetry. The symmetry groups
of such tilings are of types p3, p31m, p4, p4g, and p6. There are no isohedral
tilings with symmetry groups p3m1, p4m, or p6m that have polyominoes or
polyiamonds as fundamental domains. We display the algorithms' output and give
enumeration tables for small values of n. This expands on our earlier works
(Fukuda et al 2006, 2008).

Consider $n$ sensors whose positions are represented by $n$ uniform,
independent and identically distributed random variables assuming values in the
open unit interval $(0,1)$. A natural way to guarantee connectivity in the
resulting sensor network is to assign to each sensor as its range, the maximum
of the two possible distances to its two neighbors. The interference at a given
sensor is defined as the number of sensors that have this sensor within their
range. In this paper we prove that the expected maximum interference of the
sensors is $\Theta (\sqrt{\ln n})$.

In this paper we consider finding a geometric minimum-sum dipolar spanning
tree in R^3, and present an algorithm that takes O(n^2 log^2 n) time using
O(n^2) space, thus almost matching the best known results for the planar case.
Our solution uses an interesting result related to the complexity of the common
intersection of n balls in R^3, of possible different radii, that are all
tangent to a given point p.

The coverage problem in wireless sensor networks deals with the problem of
covering a region or parts of it with sensors. In this paper, we address the
problem of covering a set of line segments in sensor networks. A line segment `
is said to be covered if it intersects the sensing regions of at least one
sensor distributed in that region. We show that the problem of ?nding the
minimum number of sensors needed to cover each member in a given set of line
segments in a rectangular area is NP-hard.

We present a simple randomized scheme for triangulating a set $P$ of $n$
points in the plane, and construct a kinetic data structure which maintains the
triangulation as the points of $P$ move continuously along piecewise algebraic
trajectories of constant description complexity. Our triangulation scheme
experiences an expected number of $O(n^2\beta_{s+2}(n)\log^2n)$ discrete
changes, and handles them in a manner that satisfies all the standard
requirements from a kinetic data structure: compactness, efficiency, locality
and responsiveness.

We first describe a reduction from the problem of lower-bounding the number
of distinct distances determined by a set $S$ of $s$ points in the plane to an
incidence problem between points and a certain class of helices (or parabolas)
in three dimensions. We offer conjectures involving the new setup, but are
still unable to fully resolve them.

We consider the problem of monitoring an art gallery modeled as a polygon,
the edges of which are arcs of curves, with edge or mobile guards. Our focus is
on piecewise-convex polygons, i.e., polygons that are locally convex, except
possibly at the vertices, and their edges are convex arcs. We transform the
problem of monitoring a piecewise-convex polygon to the problem of 2-dominating
a properly defined triangulation graph with edges or diagonals, where
2-dominance requires that every triangle in the triangulation graph has at
least two of its vertices in its 2-dominating set.

The convergence problem of the Laplace-Beltrami operators plays an essential
role in the convergence analysis of the numerical simulations of some important
geometric partial differential equations which involve the operator. In this
note we present a new effective and convergent algorithm to compute discrete
Laplace-Beltrami operators acting on functions over surfaces. We prove a
convergence theorem for our discretization. To our knowledge, this is the first
convergent algorithm of discrete Laplace-Beltrami operators over surfaces for
functions on general surfaces.

In a balloon drawing of a tree, all the children under the same parent are
placed on the circumference of the circle centered at their parent, and the
radius of the circle centered at each node along any path from the root
reflects the number of descendants associated with the node.

It has been shown by Indyk and Sidiropoulos [IS07] that any graph of genus
g>0 can be stochastically embedded into a distribution over planar graphs with
distortion 2^O(g). This bound was later improved to O(g^2) by Borradaile, Lee
and Sidiropoulos [BLS09]. We give an embedding with distortion O(log g), which
is asymptotically optimal. Apart from the improved distortion, another
advantage of our embedding is that it can be computed in polynomial time. In
contrast, the algorithm of [BLS09] requires solving an NP-hard problem.

In this paper, we study the query version of the largest empty space
recognition problem. Here, a set of $n$ points $P$ is given in a bounded 2D
region. The objective is to preprocess $P$ such that given any arbitrary query
point $q$, the largest empty region of some desired shape that contains $q$ but
does not contain any point in $P$ can be reported efficiently.

Given a set $P$ of $n$ points in the plane, we show how to compute in $O(n
\log n)$ time a subgraph of their Delaunay triangulation that has maximum
degree 7 and is a strong planar $t$-spanner of $P$ with $t =(1+ \sqrt{2})^2
*\delta$, where $\delta$ is the spanning ratio of the Delaunay triangulation.
Furthermore, given a Delaunay triangulation, we show a distributed algorithm
that computes the same bounded degree planar spanner in O(n) time.

We prove that Y_6 is a spanner. Y_6 is the Yao graph on a set of planar
points, which has an edge from each point x to a closest point y within each of
the six angular cones of 60 deg surrounding x.

A single-vertex origami is a piece of paper with straight-line rays called
creases emanating from a fold vertex placed in its interior or on its boundary.
The Single-Vertex Origami Flattening problem asks whether it is always possible
to reconfigure the creased paper from any configuration compatible with the
metric, to a flat, non-overlapping position, in such a way that the paper is
not torn, stretched and, for rigid origami, not bent anywhere except along the
given creases.

Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$
can be probabilistically embedded into a graph of genus $g-1$ with constant
distortion. Viewing a graph of genus $g$ as embedded on the surface of a sphere
with $g$ handles attached, Indyk and Sidiropoulos' method gives an embedding
into a distribution over planar graphs with distortion $2^{O(g)}$, by
iteratively removing the handles. By removing all $g$ handles at once, we
present a probabilistic embedding with distortion $O(g^2)$ for both orientable
and non-orientable graphs.

Higher order Delaunay triangulations are a generalization of the Delaunay
triangulation which provides a class of well-shaped triangulations, over which
extra criteria can be optimized. A triangulation is order-$k$ Delaunay if the
circumcircle of each triangle of the triangulation contains at most $k$ points.
In this paper we study lower and upper bounds on the number of higher order
Delaunay triangulations, as well as their expected number for randomly
distributed points.

This paper defines the Arrwwid number of a recursive tiling (or space-filling
curve) as the smallest number w such that any ball Q can be covered by w tiles
(or curve sections) with total volume O(vol(Q)). Recursive tilings and
space-filling curves with low Arrwwid numbers can be applied to optimise disk,
memory or server access patterns when processing sets of points in
d-dimensional space. This paper presents recursive tilings and space-filling
curves with optimal Arrwwid numbers.

It is known that in the Minkowski sum of $r$ polytopes in dimension $d$, with
$r<d$, the number of vertices of the sum can potentially be as high as the
product of the number of vertices in each summand. However, the number of
vertices for sums of more polytopes was unknown so far.

We develop a tropical analogue of the classical double description method
allowing one to compute an internal representation (in terms of vertices) of a
polyhedron defined externally (by inequalities). The heart of the tropical
algorithm is a characterization of the extreme points of a polyhedron in terms
of a system of constraints which define it. We show that checking the
extremality of a point reduces to checking whether there is only one minimal
strongly connected component in an hypergraph.

Given a family of k disjoint connected polygonal sites in general position
and of total complexity n, we consider the farthest-site Voronoi diagram of
these sites, where the distance to a site is the distance to a closest point on
it. We show that the complexity of this diagram is O(n), and give an O(n log^3
n) time algorithm to compute it. We also prove a number of structural
properties of this diagram. In particular, a Voronoi region may consist of k-1
connected components, but if one component is bounded, then it is equal to the
entire region.

Let $G$ be a (possibly disconnected) planar subdivision and let $D$ be a
probability measure over $\R^2$. The current paper shows how to preprocess
$(G,D)$ into an O(n) size data structure that can answer planar point location
queries over $G$. The expected query time of this data structure, for a query
point drawn according to $D$, is $O(H+1)$, where $H$ is a lower bound on the
expected query time of any linear decision tree for point location in $G$. This
extends the results of Collette et al (2008, 2009) from connected planar
subdivisions to disconnected planar subdivisions.

We present an efficient algorithm for computing a function that minimizes the
number of critical points among all functions within a prescribed distance d
from a given input function. The result is achieved by establishing a
connection between discrete Morse theory and persistent homology. Our method
completely removes homological noise with persistence less than 2d,
constructively proving that the lower bound on the number of critical points
given by the stability theorem of persistent homology is tight in dimension two
for any input function.

Two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ admit a geometric simultaneous
embedding if there exists a set of points P and a bijection M: P -> V that
induce planar straight-line embeddings both for $G_1$ and for $G_2$. While it
is known that two caterpillars always admit a geometric simultaneous embedding
and that two trees not always admit one, the question about a tree and a path
is still open and is often regarded as the most prominent open problem in this
area.

This article considers the problem of solving a system of $n$ real polynomial
equations in $n+1$ variables. We propose an algorithm based on Newton's method
and subdivision for this problem. Our algorithm is intended only for
nondegenerate cases, in which case the solution is a 1-dimensional curve. Our
first main contribution is a definition of a condition number measuring
reciprocal distance to degeneracy that can distinguish poor and well
conditioned instances of this problem.

The 3D tree visualization faces multiple challenges: the election of an
appropriate layout, the use of the interactions that make the data exploration
easier and a metaphor that helps in the process of information understanding. A
good combination of these elements will result in a visualization that
effectively conveys the key features of a complex structure or system to a wide
range of users and permits the analytical reasoning process. In previous works
we presented the Spherical Layout, a technique for 3D tree visualization that
provides an excellent base to achieve those key features.

An n-simplex is said to be n-well-centered if its circumcenter lies in its
interior. We introduce several other geometric conditions and an algebraic
condition that can be used to determine whether a simplex is n-well-centered.
These conditions, together with some other observations, are used to describe
restrictions on the local combinatorial structure of simplicial meshes in which
every simplex is well-centered.

We present a new and simple randomized algorithm for constructing the
Delaunay triangulation using nearest neighbor graphs for point location. Under
suitable assumptions, it runs in linear expected time for points in the plane
with polynomially bounded spread, i.e., if the ratio between the largest and
smallest pointwise distance is polynomially bounded. This also holds for point
sets with bounded spread in higher dimensions as long as the expected
complexity of the Delaunay triangulation of a sample of the points is linear in
the sample size.

In this paper, we present algorithms for computing approximate hulls and
centerpoints for collections of matrices in positive definite space. There are
many applications where the data under consideration, rather than being points
in a Euclidean space, are positive definite (p.d.) matrices. These applications
include diffusion tensor imaging in the brain, elasticity analysis in
mechanical engineering, and the theory of kernel maps in machine learning. Our
work centers around the notion of a horoball: the limit of a ball fixed at one
point whose radius goes to infinity.

Given a set $\Sigma$ of $n$ hyperspheres in $\mathbb{E}^d$, $d\ge{}3$, having
$m$ distinct radii, we show that the worst-case combinatorial complexity of the
convex hull $CH_d(\Sigma)$ of $\Sigma$ is $O(m n^{\lfloor\frac{d}{2}\rfloor})$.
To the best of our knowledge, this is the first upper bound on the worst-case
combinatorial complexity of the convex hull of a set of hyperspheres that
depends not only on the number of hyperspheres, but also on the number of
distinct radii.

A memoryless routing algorithm is one in which the decision about the next
edge on the route to a vertex t for a packet currently located at vertex v is
made based only on the coordinates of v, t, and the neighbourhood, N(v), of v.
The current paper explores the limitations of such algorithms by showing that,
for any (randomized) memoryless routing algorithm A, there exists a convex
subdivision on which A takes Omega(n^2) expected time to route a message
between some pair of vertices.

Topological methods such as persistent homology are powerful tools for data
analysis of high-dimensional data sets but these methods almost exclusively
rely on thresholding techniques. However, in noisy data sets thesholding does
not always allow for the recovery of topological information. We present a
computationally-efficient algorithm to allow for topological data analysis on
noisy high-dimensional point cloud data sets. In many cases, the algorithm
returns data that has so few outliers that there is no need to threshold the
data before performing topological analysis.

Given a computer model of a physical object, it is often quite difficult to
visualize and quantify any global effects on the shape representation caused by
local uncertainty and local errors in the data. This problem is further
amplified when dealing with hierarchical representations containing varying
levels of detail and / or shapes undergoing dynamic deformations. In this
paper, we compute, quantify and visualize the complementary topological and
geometrical features of 3D shape models, namely, the tunnels, pockets and
internal voids of the object.

For a set of n points in the plane, we consider the axis--aligned (p,k)-Box
Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together
contain n-k points. In this paper, we consider the boxes to be either squares
or rectangles, and we want to minimize the area of the largest box. For general
p we show that the problem is NP-hard for both squares and rectangles. For a
small, fixed number p, we give algorithms that find the solution in the
following running times:

In greedy geometric routing, messages are passed in a network embedded in a
metric space according to the greedy strategy of always forwarding messages to
nodes that are closer to the destination. We show that greedy geometric routing
schemes exist for the Euclidean metric in R^2, for 3-connected planar graphs,
with coordinates that can be represented succinctly, that is, with O(log n)
bits, where n is the number of vertices in the graph. Moreover, our embedding
strategy introduces a coordinate system for R^2 that supports distance
comparisons using our succinct coordinates.

Inference of topological and geometric attributes of a hidden manifold from
its point data is a fundamental problem arising in many scientific studies and
engineering applications. In this paper we present an algorithm to compute a
set of loops from a point data which approximates a {\em shortest} basis of the
one dimensional homology group $\homo(M)$ of the sampled manifold $M$. Previous
results addressed the issue of computing the rank of the homology groups from
point data, but there is no result on approximating the shortest basis of a
manifold from its point sample.

We consider the directed Hausdorff distance between point sets in the plane,
where one or both point sets consist of imprecise points. An imprecise point is
modelled by a disc given by its centre and a radius. The actual position of an
imprecise point may be anywhere within its disc. Due to the direction of the
Hausdorff Distance and whether its tight upper or lower bound is computed there
are several cases to consider. For every case we either show that the
computation is NP-hard or we present an algorithm with a polynomial running
time.

We give the first nontrivial upper and lower bounds on the maximum volume of
an empty axis-parallel box inside an axis-parallel unit hypercube in $\RR^d$
containing $n$ points. For a fixed $d$, we show that the maximum volume is of
the order $\Theta(\frac{1}{n})$.

A set of n points in low dimensions takes Theta(n w) bits to store on a w-bit
machine. Surface reconstruction and mesh refinement impose a requirement on the
distribution of the points they process. I show how to use this assumption to
lossily compress a set of n input points into a representation that takes only
O(n) bits, independent of the word size. The loss can keep inter-point
distances to within 10% relative error while still achieving a factor of three
space savings.

We describe an algorithm for finding the tight span of a finite metric space;
the tight span is a construction for embedding arbitrary metrics into
$L_\infty$ spaces analogous to the Euclidean convex hull. Our algorithm is
incremental, and applies to any space for which the tight span is homeomorphic
to a subset of the Euclidean plane. After a new point is added to the metric
space our algorithm can update the tight span in time linear in the number of
points already added; this is optimal with respect to the size of the input, an
$n\times n$ distance matrix.

We address the problem of Minimum Enclosing Ball (MEB) and its generalization
to Minimum Enclosing Convex Polytope (MECP). Given $n$ points in a $d$
dimensional Euclidean space, we give a $O(nd/\sqrt{\epsilon})$ algorithm for
producing an enclosing ball whose radius is at most $\epsilon$ away from the
optimum. In the case of MECP our algorithm takes $O(1/\epsilon)$ iterations to
converge.

We re-examine the notion of relative $(p,\eps)$-approximations, recently
introduced in [CKMS06], and establish upper bounds on their size, in general
range spaces of finite VC-dimension, using the sampling theory developed in
[LLS01] and in several earlier studies [Pol86, Hau92, Tal94]. We also survey
the different notions of sampling, used in computational geometry, learning,
and other areas, and show how they relate to each other. We then give
constructions of smaller-size relative $(p,\eps)$-approximations for range
spaces that involve points and halfspaces in two and higher dimensions.