In k-means clustering, we are given a set of n data points in d-dimensional space R/sup d/ and an integer k the problem is to determine Rd, called centers, so as minimize mean squared distance from each point its nearest center. A popular heuristic for clustering Lloyd's (1982) algorithm. We present simple efficient implementation algorithm, which call filtering This algorithm easy implement, requiring kd-tree only major structure. establish practical efficiency two ways. First,...

Consider a set of S n data points in real d -dimensional space, R , where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess into structure, so that given query point q ∈ is the closest to can be reported quickly. Given positive ϵ, p (1 +ϵ)- approximate if its distance from within factor + ϵ) true neighbor. We show it possible O(dn log ) time and O(dn) ϵ > 0, ϵ)-approximate computed O ( c time, d,ϵ ≤ ⌈1 6d/ϵ⌉ depending only on dimension ϵ....

We present an algorithm for determining the shortest path between a source and destination on arbitrary (possibly nonconvex) polyhedral surface. The is constrained to lie surface, distances are measured according Euclidean metric. Our runs in time $O(n^2 \log n)$ requires )$ space, where n number of edges After we run our algorithm, distance from any other may be determined using standard techniques $O(\log by locating subdivision created algorithm. actual can reported $O(k + n)$, k faces...

In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, the problem is to determine k ℜd, called centers, minimize mean squared distance from each point its nearest center. No exact polynomial-time algorithms known for this problem. Although asymptotically efficient approximation exist, these not practical due extremely high constant factors involved. There many heuristics that used practice, but know no bounds on their performance.We consider...

Facility location problems are traditionally investigated with the assumption that all clients to be provided service. A significant shortcoming of this formulation is a few very distant clients, called outliers, can exert disproportionately strong influence over final solution. In paper we explore generalization various facility (K-center, K-median, uncapacitated etc) case when only specified fraction customers served. What makes harder have also select subset should get We provide...

Given a set of n points in d-dimensional Euclidean space, S ⊂ E, and query point q ∈ we wish to determine the nearest neighbor q, that is, whose distance is minimum. The goal preprocess S, such queries can be answered as efficiently possible. We assume dimension d constant independent n. Although reasonably good solutions this problem exist when small, increases performance these algorithms degrades rapidly. present randomized algorithm for approximate searching. any ǫ > 0, produce data...

Nearest neighbor searching is the problem of preprocessing a set n point points in d -dimensional space so that, given any query q , it possible to report closest rapidly. In approximate nearest searching, parameter ε > 0 given, and multiplicative error (1 + ε) allowed. We assume that dimension constant treat as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space having O ( ) time (log 1/ε −1 high-space roughly (( log )/ε /ε)). show there single approach...

The visibility graph of a set nonintersecting polygonal obstacles in the plane is an undirected whose vertex consists vertices and edges are pairs $(u,v)$ such that open line segment between u v does not intersect any obstacles. important combinatorial structure computational geometry used applications as solving problems computing shortest paths. This paper presents algorithm computes time $O(E + n\log n)$, where E number n total all

Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete graph with only O(n) edges, so that shortest path length between each pair points is not more than constant factor longer distance points. In many applications spanners, it spanner possess number additional properties: low tot al edge weight, bounded degree, and diameter. Existing research on has considered one property or other. We show possible to build...

Clustering is central to many image processing and remote sensing applications. ISODATA one of the most popular widely used clustering methods in geoscience applications, but it can run slowly, particularly with large data sets. We present a more efficient approach clustering, which achieves better running times by storing points kd-tree through modification way algorithm estimates dispersion each cluster. also an approximate version allows user further improve time, at expense lower...

We investigate the connection between spectrum of a graph, i.e. eigenvalues adjacency matrix, and complexity testing isomorphism. In particular we describe two polynomial time algorithms which test isomorphism undirected graphs whose have bounded multiplicity. If X Y are eigenvalue multiplicity m, then can be tested by an O(n4m+c) deterministic O(n2m+c) Las Vegas algorithm, where n is number vertices Y.

This paper shows that if one is willing to relax the requirement of finding true nearest neighbor, it possible achieve significant improvements in running time and at only a very small loss performance vector quantizer. The authors present three algorithms for neighbor searching: standard priority k-d tree search neighborhood graph algorithm which directed constructed point set edges join neighboring points.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML"...

Article Free Access Share on The analysis of a simple k-means clustering algorithm Authors: Tapas Kanungo Center for Automation Research, University Maryland College Park, MarylandView Profile , David M. Mount Department Computer Science, Maryland, Nathan S. Netanyahu Mathematics and Bar-Ilan University, Ramat-Gan 52900, Israel Christine Piatko Johns Hopkins Applied Physics Laboratory, Laurel, Ruth Silverman the District Columbia, Washington, DC, Angela Y. Wu Science Information Systems,...

The visibility graph of a set nonintersecting polygonal obstacles in the plane is an undirected whose vertices are and edges pairs (u, v) such that open line segment between u v does not intersect any obstacles. important combinatorial structure computational geometry used applications as solving problems computing shortest paths. An algorithm presented computes s time O(E + n log n), where E number total all

Let S be a set of n points in IR/sup d/ and let t>1 real number. A t-spanner for is directed graph having the as its vertices, such that any pair p q there path from to length at most t times Euclidean distance between p. Such called path. The spanner diameter defined smallest integer D containing edges. Randomized deterministic algorithms are given constructing t-spanners consisting O(n) edges O(log n) diameter. Also, it shown how maintain randomized under random insertions deletions....

A strategy is presented to find a set of points that yields Conforming Delaunay tetrahedralization three-dimensional Piecewise-Linear complex (PLC). This algorithm novel because it imposes no angle restrictions on the input PLC. In process, an described computes planar conforming triangulation Planar Straight-Line Graph (PSLG) such each triangle has bounded circumradius, which may be independent interest.