Expansion-based algorithms for finding single pair shortest path on surface

Finding single pair shortest paths on surface is a fundamental problem in various domains, like Geographic Information Systems (GIS) 3D applications, robotic path planning system, and surface nearest neighbor query in spatial database, etc. Currently, to solve the problem, existing algorithms must traverse the entire polyhedral surface. With the rapid advance in areas like Global Positioning System (CPS), Computer Aided Design (CAD) systems and laser range scanner, surface models axe becoming more and more complex. It is not uncommon that a surface model contains millions of polygons. The single pair shortest path problem is getting harder and harder to solve. Based on the observation that the single pair shortest path is in the locality, we propose in this paper efficient methods by excluding part of the surface model without considering them in the search process. Three novel expansion-based algorithms are proposed, namely, Naive algorithm, Rectangle-based Algorithm and Ellipse-based Algorithm. Each algorithm uses a two-step approach to find the shortest path. (1) compute an initial local path. (2) use the value of this initial path to select a search region, in which the global shortest path exists. The search process terminates once the global optimum criteria are satisfied. By reducing the searching region, the performance is improved dramatically in most cases.

Models of adding relations to an organization structure of a complete K-ary tree

This paper proposes three models of adding relations to an organization structure which is a complete K-ary tree of height H: (i) a model of adding an edge between two nodes with the same depth N, (ii) a model of adding edges between every pair of nodes with the same depth N and (iii) a model of adding edges between every pair of siblings with the same depth N. For each of the three models, an optimal depth N* is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes. (c) 2005 Elsevier B.V. All rights reserved.

Diffusion modeling of percutaneous absorption kinetics: 3. Variable diffusion and partition coefficients, consequences for stratum corneum depth profiles and desorption kinetics

Stratum corneum (SC) desorption experiments have yielded higher calculated steady-state fluxes than those obtained by epidermal penetration studies. A possible explanation of this result is a variable diffusion or partition coefficient across the SC. We therefore developed the diffusion model for percutaneous penetration and desorption to study the effects of either a variable diffusion coefficient or variable partition coefficient in the SC over the diffusion path length. Steady-state flux, lag time, and mean desorption time were obtained from Laplace domain solutions. Numerical inversion of the Laplace domain solutions was used for simulations of solute concentration-distance and amount penetrated (desorbed)-time profiles. Diffusion and partition coefficients heterogeneity were examined using six different models. The effect of heterogeneity on predicted flux from desorption studies was compared with that obtained in permeation studies. Partition coefficient heterogeneity had a more profound effect on predicted fluxes than diffusion coefficient heterogeneity. Concentration-distance profiles show even larger dependence on heterogeneity, which is consistent with experimental tape-stripping data reported for clobetasol propionate and other solutes. The clobetasol propionate tape-stripping data were most consistent with the partition coefficient decreasing exponentially for half the SC and then becoming a constant for the remaining SC. (C) 2004 Wiley-Liss, Inc.

Multiple paths extraction in images using a constrained expanded trellis

Single shortest path extraction algorithms have been used in a number of areas such as network flow and image analysis. In image analysis, shortest path techniques can be used for object boundary detection, crack detection, or stereo disparity estimation. Sometimes one needs to find multiple paths as opposed to a single path in a network or an image where the paths must satisfy certain constraints. In this paper, we propose a new algorithm to extract multiple paths simultaneously within an image using a constrained expanded trellis (CET) for feature extraction and object segmentation. We also give a number of application examples for our multiple paths extraction algorithm.

Predictive regression equations and clinical uses of peripheral pulse timing characteristics in children

Studies have shown that increased arterial stiffening can be an indication of cardiovascular diseases like hypertension. In clinical practice, this can be detected by measuring the blood pressure (BP) using a sphygmomanometer but it cannot be used for prolonged monitoring. It has been established that pulse wave velocity (PWV) is a direct measure of arterial stiffening but its usefulness is hampered by the absence of non-invasive techniques to estimate it. Pulse transit time (PTT) is a simple and non-invasive method derived from PWV. However, limited knowledge of PTT in children is found in the present literature. The aims of this study are to identify independent variables that confound PTT measure and describe PTT regression equations for healthy children. Therefore, PTT reference values are formulated for future pathological studies. Fifty-five Caucasian children (39 male) aged 8.4 +/- 2.3 yr (range 5-12 yr) were recruited. Predictive equations for PTT were obtained by multiple regressions with age, vascular path length, BP indexes and heart rate. These derived equations were compared in their PWV equivalent against two previously reported equations and significant agreement was obtained (p < 0.05). Findings herein also suggested that PTT can be useful as a continuous surrogate BP monitor in children.

Age-related factors that confound peripheral pulse timing characteristics in Caucasian children

Characteristics obtained from peripheral pulses can be used to assess the status of cardiovascular system of subjects. However, nonintrusive techniques are preferred when prolonged monitoring is required for their comfort. Pulse transit time ( PTT) measurement has showed its potentials to monitor timing changes in peripheral pulse in cardiovascular and respiratory studies. In children, the common peripheries used for these studies are fingers or toes. Presently, there is no known study conducted on children to investigate the possible physiologic parameters that can confound PTT measure at these sites. In this study, PTT values from both peripheral sites were recorded from 55 healthy Caucasian children ( 39 male) with mean age of 8.4 +/- 2.3 years ( range 5 - 12 years). Peripheries' path length, heart rate, systolic blood pressure, diastolic blood pressure ( DBP) and mean arterial pressure ( MAP) were measured to investigate their contributions to PTT measurement. The results reveal that PTT is significantly related to all parameters ( P< 0.05), except for DBP and MAP. Age is observed to be the dominant factor that affects PTT at both peripheries in a child. Regression equations for PTT were derived for measuring from a finger and toe, ( 6.09 age + 189.2) ms and ( 6.70 age + 243.0) ms, respectively.

Assessing the cellular transmembrane electrical potential difference on the hepatic uptake of palmitate

Understanding the driving forces for the hepatic uptake of endogenous and exogenous substrates in isolated cells and organs is fundamental to describing the underlying hepatic physiology/pharmacology. In this study we investigated whether uptake of plasma protein-bound [H-3]-palmitate across the hepatocyte wall is governed by the transmembrane electrical potential difference (PD). Uptake was studied in isolated hepatocytes and isolated perfused rat livers (IPL). Protein-binding and vasoactive properties of the different perfusates were determined using in vitro heptane/buffer partitioning studies and the multiple indicator dilution (MID) technique in the IPL, respectively. Altering hepatocyte PD by perfusate ion substitution resulted in either a substantial depolarization (-14 +/- 1 mV, n = 12, mean +/- S.E., substituting choline for Na+) or hyperpolarization (-46 +/- 3 mV, n = 12, mean +/- S.E., substituting nitrate for Cl-). Perfusate ion substitution also affected the equilibrium binding constant for the palmitate-albumin complex. IPL studies suggested that, other than with gluconate buffer, hepatic [H-3]-palmitate extraction was not affected by the buffer used, implying PD was not a determinant of extraction. [H-3]-Palmitate extraction was much lower (p < 0.05) when gluconate was substituted for Cl- ion. This work contrasts with that for the extraction of [H-3]-alanine where hepatic extraction fraction was significantly reduced during depolarization. Changing the albumin concentration did not affect hepatocyte PD, and [H-3]-palmitate clearance into isolated hepatocytes was not affected by the buffers used. MID studies with vascular and extravascular references revealed that, with the gluconate substituted buffer, the extravascular volume possibly increased the diffusional path length thus explaining reduced [H-3]-palmitate extraction fraction in the IPL.

Geodesics without differential equations: general relativistic calculations for introductory modern physics classes

Introductory courses covering modem physics sometimes introduce some elementary ideas from general relativity, though the idea of a geodesic is generally limited to shortest Euclidean length on a curved surface of two spatial dimensions rather than extremal aging in spacetime. It is shown that Epstein charts provide a simple geometric picture of geodesics in one space and one time dimension and that for a hypothetical uniform gravitational field, geodesics are straight lines on a planar diagram. This means that the properties of geodesics in a uniform field can be calculated with only a knowledge of elementary geometry and trigonometry, thus making the calculation of some basic results of general relativity accessible to students even in an algebra-based survey course on physics.

Quantum computation as geometry

Quantum computers hold great promise for solving interesting computational problems, but it remains a challenge to find efficient quantum circuits that can perform these complicated tasks. Here we show that finding optimal quantum circuits is essentially equivalent to finding the shortest path between two points in a certain curved geometry. By recasting the problem of finding quantum circuits as a geometric problem, we open up the possibility of using the mathematical techniques of Riemannian geometry to suggest new quantum algorithms or to prove limitations on the power of quantum computers.

Confounding physiologic parameters in pulse transit time monitoring of children

Pulse Transit Time (PTT) measurement has showed potential in non-invasive monitoring of changes in blood pressure. In children, the common peripheral sites used for these studies are a finger or toe. Presently, there are no known studies conducted to investigate any possible physiologic parameters affecting PTT measurement at these sites for children. In this study, PTT values of both peripheral sites were recorded from 64 children in their sitting posture. Their mean age with standard deviation (SD) was 8.2 2.6years (ranged 3 to 12years). Subjects' peripheries path length, heart rate (HR), systolic (SBP) and diastolic blood pressure (DBP) were measured to investigate any contributions to PTT measurement. The peripheral pulse timing characteristic measured by photoplethysmography (PPG) shows a 59.5 8.5ms (or 24.8 0.4%) difference between the two peripheries (p

Right ventricle extraction by low level and model-based algorithm

In this paper we present an algorithm as the combination of a low level morphological operation and model based Global Circular Shortest Path scheme to explore the segmentation of the Right Ventricle. Traditional morphological operations were employed to obtain the region of interest, and adjust it to generate a mask. The image cropped by the mask is then partitioned into a few overlapping regions. Global Circular Shortest Path algorithm is then applied to extract the contour from each partition. The final step is to re-assemble the partitions to create the whole contour. The technique is deemed quite reliable and robust, as this is illustrated by a very good agreement between the extracted contour and the expert manual drawing output.

Surface k-NN query processing

A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database. For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.