8446216
Balanced aspect ratio trees: combining the advantages of k-d trees and octrees
Given a set S of n points on Rd, we show, for fixed d, how to construct in O(nlogn) time a data structure we call the balanced aspect ratio (BAR) tree. A BAR tree is a binary space partition tree on S that has O(logn) depth in which every region is convex and “fat” (that is, has a bounded aspect ratio). While previous hierarchical data structures such as k-d trees, quadtrees, octrees, fair-split trees, and balanced box decompositions can guarantee some of these properties, we know of no previous data structure that combines all of these properties simultaneously. The BAR tree data structure has numerous applications ranging from geometric searching problems in fixed dimensional space to the visualization of graphs and three-dimensional worlds.
8530273
Drawing Planar Graphs with Large Vertices and Thick Edges
We consider the problem of representing size information in the edges and vertices of a planar graph. Such information can be used, for example, to depict a network of computers and information traveling through the network. We present an efficient linear-time algorithm which draws edges and vertices of varying 2-dimensional areas to represent the amount of information flowing through them. The algorithm avoids all occlusions of nodes and edges, while still drawing the graph on a compact integer grid.
1270229
Fast Randomized Parallel Methods for Planar Convex Hull Construction
Abstract We present a number of efficient parallel algorithms for constructing 2-dimensional convex hulls on a randomized CRCW PRAM. Specifically, we show how to build the convex hull of n presorted points in the plane in O(1) time using O(n log n) work, with n-exponential probability, or, alternately, in O ( log ∗ n) time using O(n) work, with n-exponential probability. We also show how to find the convex hull of n unsorted planar points in O(log n) time using O(n log h) work, with n-exponential probability, where h is the number of edges in the convex hull (h is O(n), but can be as small as O(1)). Our algorithm for unsorted inputs depends on the use of new in-place procedures, that is, procedures that are defined on a subset of elements in the input and that work without reordering the input. In order to achieve our n-exponential confidence bounds we use a new parallel technique called failure sweeping.
15586236
Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings
We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as being O(1) or sometimes even an arbitrary parameter. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call “subtree separation.” We investigate both upward and non-upward drawings, achieving area bounds of O(n log n) and O(n log log n), respectively, and we show that, at least in the case of upward drawings, our area bound is optimal to within constant factors.
14677263
Teaching the analysis of algorithms with visual proofs
We describe an approach for visually teaching important proofs in the Junior-Senior level course on the design and analysis of data structures and algorithms (CS7/DS&amp;A). The main idea of this educational paradigm is to justify important claims about data structures and algorithms by using pictures that visualize proofs so clearly that the pictures can qualify as proofs themselves. The advantage of using this approach for DS&amp;A is that it augments or even replaces inductive arguments that many students find difficult. Moreover, this paradigm communicates important algorithmic facts in a compelling way for students who are more visually-oriented. We illustrate this technique by giving examples of visual proofs of several key concepts in DS&amp;A.
8676248
Authenticated Dictionaries for Fresh Attribute Credentials
We describe several schemes for efficiently populating an authenticated dictionary with fresh credentials. The thrust of this effort is directed at allowing for many data authors, called sources, to collectively publish information to a common repository, which is then distributed throughout a network to allow for authenticated queries on this information. Authors are assured of their contributions being added to the repository based on cryptographic receipts that the repository returns after performing the updates sent by an author. While our motivation here is the dissemination of credential status data from multiple credential issuers, applications of this technology also include time stamping of documents, document version integrity control, and multiple-CA certificate revocation management, to name just a few.
15752591
Satisficing anytime action search for behavior-based voting
Within the field of behavior-based robotics, a useful and popular technique for robot control is that of utilitarian voting, where behaviors representing objectives assign utilities to candidate actions. Utilitarian voting allows for distributed, modular control but is not well suited to systems with very high resolution or several, dependent degrees of freedom. Past systems have depended on exhaustive searches that choose the action with the highest combined utility. We present, instead, a framework that casts the action search problem as an anytime algorithm. This allows directed searches to be used with time limit constraints. Aspiration-based satisficing additionally helps to reduce CPU usage. In experiments so far, we have decreased CPU usage by UP to 42% while causing result quality to be no more than 6% worse.
451273
Comparing the usefulness of video and map information in navigation tasks
One of the fundamental aspects of robot teleoperation is the ability to successfully navigate a robot through an environment. We define successful navigation to mean that the robot minimizes collisions and arrives at the destination in a timely manner. Often video and map information is presented to a robot operator to aid in navigation tasks. This paper addresses the usefulness of map and video information in a navigation task by comparing a side-by-side (2D) representation and an integrated (3D) representation in both a simulated and a real world study. The results suggest that sometimes video is more helpful than a map and other times a map is more helpful than video. From a design perspective, an integrated representation seems to help navigation more than placing map and video side-by-side.
43673902
Coordinated target assignment and intercept for unmanned air vehicles
Presents an end-to-end solution to the battlefield scenario where M unmanned air vehicles are assigned to strike N known targets, in the presence of dynamic threats. The problem is decomposed into the subproblems of (1) cooperative target assignment, (2) coordinated UAV intercept, (3) path planning, and (4) feasible trajectory generation. The design technique is based on a hierarchical approach to coordinated control. Detailed simulation results are presented.
13562077
Satisficing Equilibria: A Non-Classical Theory of Games and Decisions
Satisficing, or being “good enough,” is the fundamental obligation of rational decision makers. We cannot rationally choose an option, even when we do not know of anything better, unless we know it is good enough. Unfortunately, we are not often in the position of knowing that there could be no better option, and hence that the option must be good enough. A complete search through all logical possibilities is often impractical, particularly in multi-agent contexts, due to excessive computational difficulty, modeling complexity, and uncertainty. It can be equally impractical, if it is even possible, to determine the cost of the additional required search to find an option that is good enough. In a departure from the traditional notion of satisficing as a species of bounded rationality, satisficing is here redefined in terms of a notion of intrinsic rationality. Epistemic utility theory serves as the philosophical foundation of a new praxeological decision-making paradigm of satisficing equilibria that is applicable to both single- and multiple-agent scenarios. All interagent relationships are modeled by an interdependence function that explicitly accommodates both self and group interest, from which multilateral and unilateral selectability and rejectability mass functions can be derived and compared via the praxeic likelihood ratio test.
17845810
A binary-categorization approach for classifying multiple-record Web documents using application ontologies and a probabilistic model
The amount of information available on the World Wide Web has been increasing dramatically in recent years. To enhance speedy searching and retrieving Web documents of interest, researchers and practitioners have partially relied on various information retrieval techniques. We propose a probabilistic model to classify Web documents into relevant documents and irrelevant documents with respect to a particular application ontology, which is a conceptual-model snippet of standard ontologies. Our probabilistic model is based on multivariate statistical analysis and is different from the conventional probabilistic information retrieval models. The experiments we have conducted on a set of representative Web documents indicate that the proposed probabilistic model is promising in binary-categorization of multiple-record Web documents.