8900571
Computing a Segment Center for a Planar Point Set
\indent Given a set $S$ of $n$ points in the plane and a segment $e$, a {\em center placement} of $e$ is a placement (allowing translation and rotation) that minimizes the maximum distance from $e$ to the points of $S$. We present an algorithm for computing a center placement for $S$, whose running time is $O(n^{2} \alpha (n) \, \mbox {log} ^{3}n),$ where $\alpha (n)$ is the inverse Ackermann function. The algorithm makes use of the parametric searching technique of Megiddo.
2273352
Near-Linear Time Approximation Algorithms for Curve Simplification
AbstractWe consider the problem of approximating a polygonal
 curve P under a given error criterion by another
 polygonal curve P’ whose vertices are a
 subset of the vertices of P. The goal is to minimize
 the number of vertices of P’ while ensuring that the
 error between P’ and P is below a certain threshold.
 We consider two different error measures: 
 Hausdorff and Frechet. For both error criteria, we present
 near-linear time approximation algorithms that, given a
 parameter ε > 0, compute a simplified polygonal
 curve P’ whose error is less than ε and
 size at most the size of an optimal simplified
 polygonal curve with error ε/2. We consider
 monotone curves in ℝ2 in the case of the Hausdorff error measure
 under the uniform distance metric
 and arbitrary curves in any dimension for the Frechet error measure
 under Lp metrics. 
 We present
 experimental results demonstrating that our algorithms
 are simple and fast, and produce close to optimal
 simplifications in practice.
1009358
Efficient algorithms for bichromatic separability
A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding whether two sets of n points in 3-space can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double-wedge. The latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.
1016609
A 2D kinetic triangulation with near-quadratic topological changes
A triangulation of a set <i>S</i> of points in the plane is a subdivision of the convex hull of <i>S</i> into triangles whose vertices are points of <i>S</i>. Given a set <i>S</i> of <i>n</i> points in ℝ<sup>3</sup>, each moving independently, we wish to maintain a triangulation of S. The triangulation needs to be updated periodically as the points in <i>S</i> move, so the goal is to maintain a triangulation with small number of topological events, each being the insertion or deletion of an edge. We propose a kinetic data structure (KDS) that processes n<sup>2</sup> 2<sup>O(√log n•log log n )</sup> topological events, with high probability, if the trajectories of input points are algebraic curves of fixed degree. Each topological event can be processed in <i>O</i>(log <i>n</i>) time. This is the first known KDS for maintaining a triangulation that processes near-quadratic number of topological events, and almost matches the Ω(<i>n</i><sup>2</sup>) lower bound, [1]. The number of topological events can be reduced to nk • 2<sup>O(√log k•log log n )</sup> if only <i>K</i> of the points are moving.
14529095
Approximating Shortest Paths on a Nonconvex Polyhedron
We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in ${\mathbb R}^3$ and two points s and t on P, constructs a path on P between s and t whose length is at most ${7(1+{\varepsilon})} dP(s,t), where dP(s,t) is the length of the shortest path between s and t on P, and ${\varepsilon} > 0$ is an arbitrarily small positive constant. The algorithm runs in O(n5/3 log5/3 n) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n8/5 log8/5 n) time and returns a path whose length is at most ${15(1+{\varepsilon})} d_{P}(s,t)$.
9832346
Computing envelopes in four dimensions with applications
Let <inline-equation> <f> <sc>F</sc></f> </inline-equation> be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of <inline-equation> <f> <sc>F</sc></f>  </inline-equation> in expected time O(n<supscrpt>d+ε</supscrpt>), for any ε>0. For d=3, by combining this algorithm with the point location technique of Preparata and Tamassia, we can compute, in randomized expected time O(n<supscrpt>3+ε</supscrpt>) for any ε>0, a data structure of size O(n<supscrpt>3+ε</supscrpt>) that, given any query point q, can determine in O(log<supscrpt>2</supscrpt>n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the biggest stick in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in time O(n<supscrpt>17/11+ε</supscrpt>), for any ε>0 improving previous solutions that run in time O(n<supscrpt>8/5+ε</supscrpt>). We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane, and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n<supscrpt>3+ε</supscrpt>) storage and preprocessing time, for any ε>0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.
16920879
A Pragmatic Solution to an Indian Accented English Speech Synthesizer Using Residual Excited Linear Predictive Coded Voice
This paper elucidates a practical solution to an Indian accented English text to speech synthesizing system. The paper covers the complete procedure to generate the speech signal of the text, in Indian accented voice. The technique described considers the various prosodic features that need to be incorporated into the synthesized speech to make it appear natural and in the way an Indian speaks. The paper describes the complete method for synthesizing the speech including the pre-processing of the text and prosody analysis in the Indian style of speaking. The diphones extracted from an Indian’s voice are coded using Residual Excited Linear Predictive (RELP) coding technique and the resulting formants and residual values of the diphones are used to resynthesize the final output speech for the text to be synthesized. ‘PALSA’ – an Indian accented English speech synthesizer has been successfully implemented using the mentioned technique to produce the Indian accented speech and is described in this paper.