15785799
Semi-online maintenance of geometric optima and measures
We give the first nontrivial worst-case results for dynamic versions of various basic geometric optimization and measure problems under the semi-online model, where during the insertion of an object we are told when the object is to be deleted. Problems that we can solve with sublinear update time include the Hausdorff distance of two point sets, discrete 1-center, largest empty circle, convex hull volume in three dimensions, volume of the union of axis-parallel cubes, and minimum enclosing rectangle. The decision versions of the Hausdorff distance and discrete 1-center problems can be solved fully dynamically. Some applications are mentioned.
15266108
Optimal output-sensitive convex hull algorithms in two and three dimensions
We present simple output-sensitive algorithms that construct the convex hull of a set ofn points in two or three dimensions in worst-case optimalO (n logh) time andO (n) space, whereh denotes the number of vertices of the convex hull.
5208277
A Space-Efficient Algorithm for Segment Intersection
We examine the space requirement for the classic linesegment intersection problem. Using so-called implicit data structures, we show how to make the standard sweep-line algorithm run in O((n + k) log 2 n) time with only O(log 2 n) extra space, where n is the number of line segments and k is the number of intersections. If division is allowed and input can be destroyed, the algorithm can run in O((n + k) log n) time with O(1) extra space.
26455402
On Enumerating and Selecting Distances
Given an n-point set, the problems of enumerating the k closest pairs and selecting the k-th smallest distance are revisited. For the enumeration problem, we give simpler randomized and deterministic algorithms with O(nlog n+k) running time in any fixed-dimensional Euclidean space. For the selection problem, we give a randomized algorithm with running time O(nlog n+n2/3k1/3log5/3n) in the Euclidean plane. We also describe output-sensitive results for halfspace range counting that are of use in more general distance selection problems. None of our algorithms requires parametric search.
133008994
A Randomized Algorithm for Online Unit Clustering
In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naive upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.
5726313
Finding the shortest bottleneck edge in a parametric minimum spanning tree
<b>The result.</b> <i>Parametric optimization problems</i> that concern graphs with continuously changing edge weights have been explored by numerous researchers, with motivation ranging from sensitivity analysis to mobile-data applications. For instance, Dey [5] has shown that for an undirected graph with <i>n</i> vertices and <i>m</i> edges where the edge weights are linear functions in one parameter ("time"), the minimum spanning tree (MST) can undergo at most <i>O</i>(<i>mn</i><sup>1/3</sup>) changes (edge swaps). Agarwal <i>et al.</i> [1] have given data structures to maintain the MST over time, with a cost of <i>O</i>(<i>n</i><sup>2/3</sup> polylog <i>n</i>) per change. Fernandez-Baca <i>et al.</i> [7] have given an algorithm to compute all changes to the MST in <i>O</i>(<i>mn</i> log <i>n</i>) total time.
13840611
Dynamic cluster formation using level set methods
Density-based clustering has the advantages for: 1) allowing arbitrary shape of cluster and 2) not requiring the number of clusters as input. However, when clusters touch each other, both the cluster centers and cluster boundaries (as the peaks and valleys of the density distribution) become fuzzy and difficult to determine. We introduce the notion of cluster intensity function (CIF) which captures the important characteristics of clusters. When clusters are well-separated, CIFs are similar to density functions. But, when clusters become closed to each other, CIFs still clearly reveal cluster centers, cluster boundaries, and degree of membership of each data point to the cluster that it belongs. Clustering through bump hunting and valley seeking based on these functions are more robust than that based on density functions obtained by kernel density estimation, which are often oscillatory or oversmoothed. These problems of kernel density estimation are resolved using level set methods and related techniques. Comparisons with two existing density-based methods, valley seeking and DBSCAN, are presented which illustrate the advantages of our approach.
20186109
Balanced information inequalities
In this correspondence, we are interested in linear information inequalities, both discrete and continuous ones. We show that every discrete information inequality is associated with a "balanced" information inequality and a set of "residual weights." To prove the inequality, it is necessary and sufficient to prove that its "balanced" version is valid and all its residual weights are nonnegative. For a continuous information inequality, we prove that it is valid if and only if its discrete counterpart is balanced and valid.
45840953
Dynamic Cluster Formation Using Level Set Methods
Density-based clustering has the advantages for (i) allowing arbitrary shape of cluster and (ii) not requiring the number of clusters as input. However, when clusters touch each other, both the cluster centers and cluster boundaries (as the peaks and valleys of the density distribution) become fuzzy and difficult to determine. In higher dimension, the boundaries become wiggly and over-fitting often occurs. We introduce the notion of cluster intensity function (CIF) which captures the important characteristics of clusters. When clusters are well-separated, CIFs are similar to density functions. But as clusters touch each other, CIFs still clearly reveal cluster centers, cluster boundaries, and, degree of membership of each data point to the cluster that it belongs. Clustering through bump hunting and valley seeking based on these functions are more robust than that based on kernel density functions which are often oscillatory or over-smoothed. These problems of kernel density estimation are resolved using Level Set Methods and related techniques. Comparisons with two existing density-based methods, valley seeking and DBSCAN, are presented to illustrate the advantages of our approach.
6323270
Capacity-achieving probability measure for conditionally Gaussian channels with bounded inputs
A conditionally Gaussian channel is a vector channel in which the channel output, given the channel input, has a Gaussian distribution with (well-behaved) input-dependent mean and covariance. We study the capacity-achieving probability measure for conditionally Gaussian channels subject to bounded-input constraints and average cost constraints. Many practical communication systems, including additive Gaussian noise channels, certain optical channels, fading channels, and interference channels fall within this framework. Subject to bounded-input constraint (and average cost constraints), we show that the channel capacity is achievable and we derive a necessary and sufficient condition for a probability measure to be capacity achieving. Under certain conditions, the capacity-achieving measure is proved to be discrete.
15943063
Enterprise Systems Success: A Measurement Model
This paper presents a validated measurement model and instrument for assessing enterprise systems success from multiple perspectives. The final validated study model employs 27 measures of the four dimensions: information quality, system quality, individual impact, and organizational impact. The model is empirically tested with survey data gathered from 27 public sector organizations that implemented SAP R/3 in the late 1990s. The study consists of an exploratory inventory survey (model building) to identify the salient success dimensions and measures, followed by a confirmatory weights survey, for testing model validity (model testing). Test results demonstrate the discriminant validity of the four dimensions, as well as their convergence on a single higher-order phenomenon: enterprise systems success (ESS). Criterion validity testing further demonstrates the additivity of the four dimensions of success, and the completeness of the resultant overarching, second-order measure of ESS.