We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let $\rho\geqslant1$ be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. Let $\varepsilon$ be any number strictly between 0 and 1. Our data structure returns a $(1+\varepsilon)$ approximation of the shortest path cost from the fixed source to a query destination in $O(\log\frac{\rho n}{\varepsilon})$ time. Afterwards, a $(1+\varepsilon)$-approximate shortest path can be reported in $O(\log n)$ time plus the complexity of the path. The data structure uses $O(\frac{\rho^2n^3}{\varepsilon^2}\log\frac{\rho n}{\varepsilon})$ space and can be built in $O(\frac{\rho^2n^3}{\varepsilon^2}(\log\frac{\rho n}{\varepsilon})^2)$ time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle.

Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let $\rho\geq 1$ be a real number. Distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any $\varepsilon\in(0,1)$ and for any two points $v_s$ and $v_d$, we give an algorithm that finds a path from $v_s$ to $v_d$ whose cost is at most $(1+\varepsilon)$ times the optimal. Our algorithm runs in $O(\frac{\rho^2\log \rho}{\varepsilon^2}n^3 \log(\frac{\rho n}\varepsilon))$ time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in $[1,\rho]\cup \{\infty\}$, the time bound of our algorithm improves to $O(\frac{\rho\log \rho}{\varepsilon}n^3 \log(\frac{\rho n}\varepsilon))$.

We present a data structure for answering approximate shortest path queries ina planar subdivision from a fixed source. Let ρ ≥ 1 be a real number.Distances in each face of this subdivision are measured by a possiblyasymmetric convex distance function whose unit disk is contained in aconcentric unit Euclidean disk, and contains a concentric Euclidean disk withradius 1/ρ. Different convex distance functions may be used for differentfaces, and obstacles are allowed. Let ε be any number strictly between 0and 1. Our data structure returns a (1+ε)approximation of the shortest path cost from the fixed source to a querydestination in O(logρn/ε) time. Afterwards, a(1+ε)-approximate shortest path can be reported in time linear in itscomplexity. The data structure uses O(ρ2 n4/ε2 log ρn/ε) space and can be built in O((ρ2 n4)/(ε2)(log ρn/ε)2) time. Our time and space bounds do not depend onany geometric parameter of the subdivision such as the minimum angle.

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in $\mathbb{R}^3$ with a total of n edges consists of $\Theta(n^2)$ connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, $\Theta(n^2k^2)$ connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an $O(n^2 k^2 \log n)$ time and $O(nk^2)$ space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.

Let /spl lscr/ /sub 1/,/spl lscr/ /sub 2/,...,/spl lscr/ /sub n/ be a (possibly infinite) sequence of nonnegative integers and /spl Sigma/ some D-ary alphabet. The Kraft-inequality states that /spl lscr/ /sub 1/,/spl lscr/ /sub 2/,...,/spl lscr/ /sub n/ are the lengths of the words in some prefix (free) code over /spl Sigma/ if and only if /spl Sigma//sub i=1//sup n/D/sup -/spl lscr/ i//spl les/1. Furthermore, the code is exhaustive if and only if equality holds. The McMillan inequality states that if /spl lscr/ /sub n/ are the lengths of the words in some uniquely decipherable code, then the same condition holds. In this paper we examine how the Kraft-McMillan inequality conditions for the existence of a prefix or uniquely decipherable code change when the code is not only required to be prefix but all of the codewords are restricted to belong to a given specific language L. For example, L might be all words that end in a particular pattern or, if /spl Sigma/ is binary, might be all words in which the number of zeros equals the number of ones.

We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝ3 with n edges in total form Θ(n2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of kconvex polyhedra with a total of n edges admits, in the worst case, Θ(n2k2)connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2k2) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.

In this paper, we show that, amongst n uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176-206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

(MATH) It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ( n 2 ). Interest has recently arisen as to what happens, both in deterministic and probabilistic situations, when the 3-dimensional points are restricted to lie on the surface of a 2-dimensional object. In this paper we consider the situation when the points are drawn from a 2-dimensional Poisson distribution with rate n over a fixed union of triangles in $\myRe^3.$ We show that with high probability the complexity of their Voronoi diagram is $\Ot n .(MATH) This implies, for example, that the complexity of the Voronoi diagram of points chosen from the surface of a general fixed polyhedron in $\myRe 3 will also be $\Ot n with high probability.

In this paper we discuss the problem of constructing minimum-cost, prefix-free codes for equiprobable words under the assumption that all codewords are restricted to belonging to an arbitrary language L. We examine how, given certain types of L, the structure of the minimum-cost code changes as n, the number of codewords, grows.