Freehand sketching is both a natural and crucial part of design, yet is unsupported by current design automation software. We are working to combine the flexibility and ease of use of paper and pencil with the processing power of a computer to produce a design environment that feels as natural as paper, yet is considerably smarter. One of the most basic steps in accomplishing this is converting the original digitized pen strokes in the sketch into the intended geometric objects using feature point detection and approximation. We demonstrate how multiple sources of information can be combined for feature detection in strokes and apply this technique using two approaches to signal processing, one using simple average based thresholding and a second using scale space.

In most classical frameworks for learning from examples, it is assumed that examples are randomly drawn and presented to the learner. In this paper, we consider the possibility of a more active learner who is allowed to choose his/her own examples. Our investigations are carried out in a function approximation setting. In particular, using arguments from optimal recovery (Micchelli and Rivlin, 1976), we develop an adaptive sampling strategy (equivalent to adaptive approximation) for arbitrary approximation schemes. We provide a general formulation of the problem and show how it can be regarded as sequential optimal recovery. We demonstrate the application of this general formulation to two special cases of functions on the real line 1) monotonically increasing functions and 2) functions with bounded derivative. An extensive investigation of the sample complexity of approximating these functions is conducted yielding both theoretical and empirical results on test functions. Our theoretical results (stated insPAC-style), along with the simulations demonstrate the superiority of our active scheme over both passive learning as well as classical optimal recovery. The analysis of active function approximation is conducted in a worst-case setting, in contrast with other Bayesian paradigms obtained from optimal design (Mackay, 1992).

Many geophysical inverse problems are ill-posed and have to be regularized. The most often used solution methods for solving ill-posed problems are based on the use of quadratic regularization that results in smooth solutions. Solutions of this type are not to be suitable when the model parameter is piecewise continuous blocky and edges are desired in the regularized solution. To avoid the smoothing of edges, which are very important attributes of an image, an edge-preserving regularization (non-quadratic regularization) term has to be employed. Total Variation (TV) regularization is one of the most effective regularization techniques for allowing sharp edges and the existence of discontinuities in the solutions. The edge-preserving regularization based on the TV method for small-scale geophysical inverse problems to the problem of estimating the acoustic velocity perturbation from a multi-source-receiver geophysical experiment is studied. The acoustic velocity perturbation is assumed to be piecewise continuous and blocky. The problem is based on linearization acoustic modeling using the framework of the single-scattering Born approximation from a known constant background medium. To solve this non-linear and ill-posed problem, an iterative scheme based on the conjugate gradient method is employed. The TV regularization method provides us with the opportunity to recover more useful information of velocity profiles from the measured seismic data. Though it requires more effort in implementing the TV term to control the smoothing and regularization parameter, the algorithm possesses the strong ability of marking the discontinuities and ensures their preservation from over-smoothing. / Geophysics

The purpose of this project was to develop a delivery system optimized for laser interstitial thermotherapy of small tumors of the breast. The proposed approach is to combine laser interstitial thermotherapy with stereotactic imaging for fiber guidance and treatment monitoring. The goals of the dissertation were to design a fiber insertion system for cylindrical diffusing tip optical fibers and to derive optimal laser parameters for coagulation of 1 cm tumor plus a surrounding 1 cm thick rim of healthy tissue. A fiber insertion system compatible with a high resolution stereotactic digital X-ray biopsy system was designed to guide the fiber into the tumor site in similar fashion to the insertion of the biopsy needle. An optical-thermal model consisting of a radiation model, a thermal model, and a coagulation model was developed and validated using ex-vivo porcine tissue. A single integrating sphere optical property measurement system and an inverse Monte Carlo algorithm were developed to measure the optical properties of ex-vivo porcine tissue at 830, 940, and 980 nm. An experimental method was developed to determine the parameters of the Arrhenius model (frequency factor (A) and activation energy (Ea)). The optical-thermal model was validated by comparing the predicted temperature and coagulation to results of laser irradiation experiments at 830, 940, and 980 nm. Using published values of the optical properties of the breast, the model predicts that a 3 cm coagulation size can be produced without vaporization in 10 min with 10.4 W at 980 and 940 nm and 13.2 W at 830 nm. The same outcome can be achieved in 20 min with 4.5 W at 980 and 940 nm and 6.1 W at 830 nm.

No description available.

No description available.

In this thesis we study approximation of negative plurisubharmonic functions by functions defined on strictly larger domains. We show that, under certain conditions, every function u that is defined on a bounded hyperconvex domain Ω in Cn and has essentially boundary values zero and bounded Monge-Ampère mass, can be approximated by an increasing sequence of functions {uj} that are defined on strictly larger domains, has boundary values zero and bounded Monge-Ampère mass. We also generalize this and show that, under the same conditions, the approximation property is true if the function u has essentially boundary values G, where G is a plurisubharmonic functions with certain properties. To show these approximation theorems we use subextension. We show that if Ω_1 and Ω_2 are hyperconvex domains in Cn and if u is a plurisubharmonic function on Ω_1 with given boundary values and with bounded Monge-Ampère mass, then we can find a plurisubharmonic function û defined on Ω_2, with given boundary values, such that û <= u on Ω and with control over the Monge-Ampère mass of û.

The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction. In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter. The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3. In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices. In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.

We study the complexity of finding so called spanner paths between arbitrary nodes in Euclidean graphs. We study both general Euclidean graphs and a special type of graphs called Integer Graphs. The problem is proven NP-complete for general Euclidean graphs with non-constant stretches (e.g. (2n)^(3/2) where n denotes the number of nodes in the graph). An algorithm solving the problem in O(2^(0.822n)) is presented. Integer graphs are simpler and for these special cases a better algorithm is presented. By using a partial order of so called Images the algorithm solves the spanner path problem using O(2^(c(\log n)^2)) time, where c is a constant depending only on the stretch.

Cette thèse concerne l'utilisation de l'interaction entre un algorithme et un expert pour la résolution de problèmes complexes, typiquement NP-difficiles. Plusieurs définitions de l'expert sont possibles. L'objectif étant d'obtenir des algorithmes dont les performances sont garanties, ce travail est centré sur les interactions avec un expert de type "oracle", plutôt que "humain". Ainsi, on s'intéresse à des compromis entre performance, coût (typiquement temps d'exécution), et quantité d'information donnée par l'oracle. Le premier objectif de cette thèse est de comprendre quel est l'état de l'art des différentes techniques interactives dans différents domaines (algorithmique distribuée et online, complexité, optimisation combinatoire). Le second objectif est centré sur l'optimisation combinatoire, et plus particulièrement les problèmes d'ordonnancement et d'empaquetage. Nous proposons un formalisme interactif pour le contexte des problèmes d'optimisations (offline). Le but est de montrer en quoi ce formalisme facilite la conception d'algorithmes d'approximation, en le situant par rapport aux techniques classiques de conception de schémas d'approximation, et en l'utilisant pour fournir de nouveaux résultats sur des problèmes d'ordonnancement et d'empaquetage. Nous avons principalement abordé deux problèmes : le "discrete Resource Sharing Scheduling Problem ($dRSSP$)" et le problème du "Multiple Strip Packing" ($MSP$). Le $dRSSP$ est un problème d'hybridation d'algorithmes. Etant donné un ensemble d'algorithmes (appelé un "portfolio"), un nombre fini de ressources (des processeurs par exemple), et un ensemble représentatif d'instances (appelé "benchmark"), le but est de distribuer ces ressources aux algorithmes afin de minimiser le temps nécessaire à la résolution de toutes les instances du benchmark, en exécutant les algorithmes en parallèle selon le modèle dit du "space sharing" . Nous avons étudié l'impact de plusieurs questions à poser à l'oracle, ainsi que comment communiquer efficacement avec ce dernier (signifiant que la réponse de l'oracle est courte), aboutissant à plusieurs schémas d'approximation. Le $MSP$ est une extension du problème célèbre du "Strip Packing" consistant à placer des rectangles dans un nombre fixé de boîtes, en minimisant la hauteur atteinte. Nous avons fourni plusieurs algorithmes/schémas d'approximation pour différentes variantes de ce problème, dans lesquelles les boîtes ont des largeurs égales/différentes, ou les rectangles doivent être placés de façon "continue" ou non (correspondant alors à un problème classique d'ordonnancement de tâches parallèles). D'une manière générale l'utilisation de l'interactivité permet d'isoler la difficulté des problèmes, et donc de les étudier différemment.