Search

Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons., Tim Ophelders: Partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Rodrigo I. Silveira: Partially funded by MICINN through project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033., Peer Reviewed, Postprint (published version)

Our aim is to develop dynamic data structures that support k-nearest neighbors (k-NN) queries for a set of n point sites in the plane in O(f(n)+k) time, where f(n) is some polylogarithmic function of n. The key component is a general query algorithm that allows us to find the k-NN spread over t substructures simultaneously, thus reducing an O(tk) term in the query time to O(k). Combining this technique with the logarithmic method allows us to turn any static k-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, O(log2⁡n/log⁡log⁡n+k) query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic geodesic k-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only k-NN data structure. More generally, we obtain a dynamic planar k-NN data structure for any type of distance functions for which we can build vertical shallow cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant-complexity, algebraic distance functions.

Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.

A key idea in many-objective optimization is to approximate the optimal Pareto front using a set of representative non-dominated solutions. The produced solution set should be close to the optimal front (convergence) and well-diversified (diversity). Recent studies have shown that measuring both convergence and diversity depends on the shape (or curvature) of the Pareto front. In recent years, researchers have proposed evolutionary algorithms that model the shape of the non-dominated front to define environmental selection strategies that adapt to the underlying geometry. This paper proposes a novel method for non-dominated front modeling using the Newton-Raphson iterative method for roots finding. Second, we compute the distance (diversity) between each pair of non-dominated solutions using geodesics, which are generalizations of the distance on Riemann manifolds (curved topological spaces). We have introduced an evolutionary algorithm within the Adaptive Geometry Estimation based MOEA (AGE-MOEA) framework, which we called AGE-MOEA-II. Computational experiments with 17 problems from the WFG and SMOP benchmarks show that AGE-MOEA-II outperforms its predecessor AGE-MOEA as well as other state-of-the-art many-objective algorithms, i.e., NSGA-III, MOEA/D, VaEA, and LMEA., Software Engineering

A key idea in many-objective optimization is to approximate the optimal Pareto front using a set of representative non-dominated solutions. The produced solution set should be close to the optimal front (convergence) and well-diversified (diversity). Recent studies have shown that measuring both convergence and diversity depends on the shape (or curvature) of the Pareto front. In recent years, researchers have proposed evolutionary algorithms that model the shape of the non-dominated front to define environmental selection strategies that adapt to the underlying geometry. This paper proposes a novel method for non-dominated front modeling using the Newton-Raphson iterative method for roots finding. Second, we compute the distance (diversity) between each pair of non-dominated solutions using geodesics, which are generalizations of the distance on Riemann manifolds (curved topological spaces). We have introduced an evolutionary algorithm within the Adaptive Geometry Estimation based MOEA (AGE-MOEA) framework, which we called AGE-MOEA-II. Computational experiments with 17 problems from the WFG and SMOP benchmarks show that AGE-MOEA-II outperforms its predecessor AGE-MOEA as well as other state-of-the-art many-objective algorithms, i.e., NSGA-III, MOEA/D, VaEA, and LMEA., Software Engineering

We present an algorithm to compute the geodesic L₁ farthest-point Voronoi diagram of m point sites in the presence of n rectangular obstacles in the plane. It takes O(nm+n log n + mlog m) construction time using O(nm) space. This is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query in O(log(n+m)) time.

Our aim is to develop dynamic data structures that support k-nearest neighbors (k-NN) queries for a set of n point sites in O(f(n) + k) time, where f(n) is some polylogarithmic function of n. The key component is a general query algorithm that allows us to find the k-NN spread over t substructures simultaneously, thus reducing a O(tk) term in the query time to O(k). Combining this technique with the logarithmic method allows us to turn any static k-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, O(log²n/log log n +k) query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic geodesic k-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only k-NN data structure. More generally, we obtain a dynamic k-NN data structure for any type of distance functions for which we can build vertical shallow cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant-complexity, algebraic distance functions.

Our aim is to develop dynamic data structures that support k-nearest neighbors (k-NN) queries for a set of n point sites in O(f(n) + k) time, where f(n) is some polylogarithmic function of n. The key component is a general query algorithm that allows us to find the k-NN spread over t substructures simultaneously, thus reducing a O(tk) term in the query time to O(k). Combining this technique with the logarithmic method allows us to turn any static k-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, O(log²n/log log n +k) query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic geodesic k-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only k-NN data structure. More generally, we obtain a dynamic k-NN data structure for any type of distance functions for which we can build vertical shallow cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant-complexity, algebraic distance functions.

In today's world, determining the boundaries of buildings on earth is a field where remote sensing specialists work extensively because of social, economic and military significance. The automatic detection of the distribution of land and buildings from aerial photographs has become a field that has been challenged by many scientists in the last 25 years. The increase in interest in this area is due to abilities of achieving high resolution, low cost images quickly. Another factor that leads to increased work on this area is the widespread use of high-resolution LIDAR data. Due to the LIDAR height data, pixel groups belonging to objects other than land can easily be obtained due to the elevation information. In this study, new methods for building boundary detection are developed using Lidar data. The seed points for the building detection algorithm are obtained by morphological operations. By using these pixel groups, a map is obtained that contains the computed geodesic distance and the areas that are candidates for buildings. By using this map, classification of buildings and non-building areas are obtained by using the graph-cut method. It has been experimentally demonstrated that the performance of the proposed method is more successful than the other building methods applied today., Günümüz dünyasında binaların yeryüzüne dağılımının tespiti uzaktan algılama uzmanlarının yoğun çalıştığı bir alandır. Çünkü bina dağılımı sosyal, ekonomik ve askeri açıdan önem arzetmektedir. Dolasıyla bina dağılımının hava fotoğraflarından otomatik tespit edilmesi son 25 yılda birçok bilim insanının uğraştığı bir alan olmaktadır. Bu alana olan ilginin artmasında yüksek çözünürlüklü, maliyeti düşük görüntülerin hızlı bir şekilde elde edilmesinin önemli bir etkisi vardır. Bu alanda yapılan çalışmaların artmasına neden olan diğer bir etmen ise yüksek çözünürlüklü LİDAR verisinin yaygınlaşmasıdır. LİDAR yükseklik verisi sayesinde araziye ait olmayan ve çevresine göre yüksekte kalan nesnelere ait piksel grupları kolayca elde edilebilmektedir. Bu çalışmada LİDAR verisi kullanılarak bina tespiti için yeni yöntemler geliştirilmiştir. Bina bulma algoritması için başlangıç noktaları morfolojik işlemler ile elde edilmiştir. Bu piksel gruplarını kullanarak hesaplanan geodezik mesafesi ile bina olabilecek alanların bilgisini içeren bir harita elde edilmektedir. Bu harita kullanılarak çizge kesme sınıflandırma yöntemi ile bina olan ve olmayan yerler elde edilmiştir. Uygulanan yöntem yardımı ile tespit edilen bina performans sonuçlarının günümüzde uygulanan diğer bina bulma yöntemlerine göre daha başarılı olduğu deneysel olarak gösterilmiştir.

In today's world, determining the boundaries of buildings on earth is a field where remote sensing specialists work extensively because of social, economic and military significance. The automatic detection of the distribution of land and buildings from aerial photographs has become a field that has been challenged by many scientists in the last 25 years. The increase in interest in this area is due to abilities of achieving high resolution, low cost images quickly. Another factor that leads to increased work on this area is the widespread use of high-resolution LIDAR data. Due to the LIDAR height data, pixel groups belonging to objects other than land can easily be obtained due to the elevation information. In this study, new methods for building boundary detection are developed using Lidar data. The seed points for the building detection algorithm are obtained by morphological operations. By using these pixel groups, a map is obtained that contains the computed geodesic distance and the areas that are candidates for buildings. By using this map, classification of buildings and non-building areas are obtained by using the graph-cut method. It has been experimentally demonstrated that the performance of the proposed method is more successful than the other building methods applied today., Günümüz dünyasında binaların yeryüzüne dağılımının tespiti uzaktan algılama uzmanlarının yoğun çalıştığı bir alandır. Çünkü bina dağılımı sosyal, ekonomik ve askeri açıdan önem arzetmektedir. Dolasıyla bina dağılımının hava fotoğraflarından otomatik tespit edilmesi son 25 yılda birçok bilim insanının uğraştığı bir alan olmaktadır. Bu alana olan ilginin artmasında yüksek çözünürlüklü, maliyeti düşük görüntülerin hızlı bir şekilde elde edilmesinin önemli bir etkisi vardır. Bu alanda yapılan çalışmaların artmasına neden olan diğer bir etmen ise yüksek çözünürlüklü LİDAR verisinin yaygınlaşmasıdır. LİDAR yükseklik verisi sayesinde araziye ait olmayan ve çevresine göre yüksekte kalan nesnelere ait piksel grupları kolayca elde edilebilmektedir. Bu çalışmada LİDAR verisi kullanılarak bina tespiti için yeni yöntemler geliştirilmiştir. Bina bulma algoritması için başlangıç noktaları morfolojik işlemler ile elde edilmiştir. Bu piksel gruplarını kullanarak hesaplanan geodezik mesafesi ile bina olabilecek alanların bilgisini içeren bir harita elde edilmektedir. Bu harita kullanılarak çizge kesme sınıflandırma yöntemi ile bina olan ve olmayan yerler elde edilmiştir. Uygulanan yöntem yardımı ile tespit edilen bina performans sonuçlarının günümüzde uygulanan diğer bina bulma yöntemlerine göre daha başarılı olduğu deneysel olarak gösterilmiştir.

Human functional Magnetic Resonance Imaging (fMRI) data are acquired while participants engage in diverse perceptual, motor, cognitive, and emotional tasks. Although data are acquired temporally, they are most often treated in a quasi-static manner. Yet, a fuller understanding of the mechanisms that support mental functions necessitates the characterization of dynamic properties. Firstly, we describe an approach employing a class of recurrent neural networks called reservoir computing, and show their feasibility and potential for the analysis of temporal properties of brain data. We show that reservoirs can be used effectively both for condition classification and for characterizing lower-dimensional "trajectories" of temporal data. Classification accuracy was approximately 90% for short clips of "social interactions" and around 70% for clips extracted from movie segments. Data representations with 12 or fewer dimensions (from an original space with over 300) attained classification accuracy within 5% of the full data. We hypothesize that such low-dimensional trajectories may provide "signatures" that can be associated with tasks and/or mental states. The approach was applied across participants (that is, training in one set of participants, and testing in a separate group), showing that representations generalized well to unseen participants. In the second part, we use fully-trained recurrent neural networks to capture and characterize spatiotemporal properties of brain events. We propose an architecture based on long short-term memory (LSTM) networks to uncover distributed spatiotemporal signatures during dynamic experimental conditions. We demonstrate the potential of the approach using naturalistic movie-watching fMRI data. We show that movie clips result in complex but distinct spatiotemporal patterns in brain data that can be classified using LSTMs (≈90% for 15-way classification), demonstrating that learned representations generalized to unseen participants.

We study continuous analogues of “vitality” for discrete network flows/paths, and consider problems related to placing segment barriers that have highest impact on a flow/path in a polygonal domain. This extends the graph-theoretic notion of “most vital arcs” for flows/paths to geometric environments. We give hardness results and efficient algorithms for various versions of the problem, (almost) completely separating hard and polynomially-solvable cases.

We study continuous analogues of “vitality” for discrete network flows/paths, and consider problems related to placing segment barriers that have highest impact on a flow/path in a polygonal domain. This extends the graph-theoretic notion of “most vital arcs” for flows/paths to geometric environments. We give hardness results and efficient algorithms for various versions of the problem, (almost) completely separating hard and polynomially-solvable cases.

We study continuous analogues of “vitality” for discrete network flows/paths, and consider problems related to placing segment barriers that have highest impact on a flow/path in a polygonal domain. This extends the graph-theoretic notion of “most vital arcs” for flows/paths to geometric environments. We give hardness results and efficient algorithms for various versions of the problem, (almost) completely separating hard and polynomially-solvable cases.

Let P be a simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. Given a set S of m sites being a subset of the vertices of P, we present the first randomized algorithm to compute the geodesic farthest-point Voronoi diagram of S in P running in expected O(n + m) time. That is, a partition of P into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic distance. This algorithm can be extended to run in expected O(n + m log m) time when S is an arbitrary set of m sites contained in P.

Localization of focal vascular lesions on brain MRI is an important component of research on the etiology of neurological disorders. However, manual annotation of lesions can be challenging, time-consuming and subject to observer bias. Automated detection methods often need voxel-wise annotations for training. We propose a novel approach for automated lesion detection that can be trained on scans only annotated with a dot per lesion instead of a full segmentation. From the dot annotations and their corresponding intensity images we compute various distance maps (DMs), indicating the distance to a lesion based on spatial distance, intensity distance, or both. We train a fully convolutional neural network (FCN) to predict these DMs for unseen intensity images. The local optima in the predicted DMs are expected to correspond to lesion locations. We show the potential of this approach to detect enlarged perivascular spaces in white matter on a large brain MRI dataset with an independent test set of 1000 scans. Our method matches the intra-rater performance of the expert rater that was computed on an independent set. We compare the different types of distance maps, showing that incorporating intensity information in the distance maps used to train an FCN greatly improves performance.

We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set S of point sites in a static simple polygon P. Our data structure allows us to insert a new site in S, delete a site from S, and ask for the site in S closest to an arbitrary query point q in P. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in P. Our data structure achieves polylogarithmic update and query times, and uses O(n log^3n log m + m) space, where n is the number of sites in S and m is the number of vertices in P. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.

The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Omega(n+m log m), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O((n+m)log (n+m)) and O(n+m log m log^2n) time, which are optimal for m=Omega(n) and m=O(n/(log^3n)), respectively. In this paper, we give a construction algorithm with O(n+m(log m+log^2 n)) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O(log n) time, then the construction time will become the optimal O(n+m log m). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O(log n) time.

In shape analysis and matching, it is often important to encode information about the relation between a given point and other points on a shape, namely, its context. To this aim, we propose a theoretically sound and efficient approach for the simulation of a discrete time evolution process that runs through all possible paths between pairs of points on a surface represented as a triangle mesh in the discrete setting. We demonstrate how this construction can be used to efficiently construct a multiscale point descriptor, called the Discrete Time Evolution Process Descriptor, which robustly encodes the structure of neighborhoods of a point across multiple scales. Our work is similar in spirit to the methods based on diffusion geometry, and derived signatures such as the HKS or the WKS, but provides information that is complementary to these descriptors and can be computed without solving an eigenvalue problem. We demonstrate through extensive experimental evaluation that our descriptor can be used to obtain accurate results in shape matching in different scenarios. Our approach outperforms similar methods and is especially robust in the presence of large nonisometric deformations, including missing parts.

Given a set of sites in a simple polygon, a geodesic Voronoi diagram partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n-gon, which improve the best known ones for m < n/polylog n. Moreover, the algorithms for the nearest-point and farthest-point Voronoi diagrams are optimal for m < n/polylog n. This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.

Background: Prokaryotic 16S ribosomal RNA (rRNA) sequences are widely used in environmental microbiology and molecular evolution as reliable markers for the taxonomic classification and phylogenetic analysis of microbes. Restricted by current sequencing techniques, the massive sequencing of 16S rRNA gene amplicons encompassing the full length of genes is not yet feasible. Thus, the selection of the most efficient hypervariable regions for phylogenetic analysis and taxonomic classification is still debated. In the present study, several bioinformatics tools were integrated to build an in silico pipeline to evaluate the phylogenetic sensitivity of the hypervariable regions compared with the corresponding full-length sequences. Results: The correlation of seven sub-regions was inferred from the geodesic distance, a parameter that is applied to quantitatively compare the topology of different phylogenetic trees constructed using the sequences from different sub-regions. The relationship between different sub-regions based on the geodesic distance indicated that V4-V6 were the most reliable regions for representing the full-length 16S rRNA sequences in the phylogenetic analysis of most bacterial phyla, while V2 and V8 were the least reliable regions. Conclusions: Our results suggest that V4-V6 might be optimal sub-regions for the design of universal primers with superior phylogenetic resolution for bacterial phyla. A potential relationship between function and the evolution of 16S rRNA is also discussed.

Background: Prokaryotic 16S ribosomal RNA (rRNA) sequences are widely used in environmental microbiology and molecular evolution as reliable markers for the taxonomic classification and phylogenetic analysis of microbes. Restricted by current sequencing techniques, the massive sequencing of 16S rRNA gene amplicons encompassing the full length of genes is not yet feasible. Thus, the selection of the most efficient hypervariable regions for phylogenetic analysis and taxonomic classification is still debated. In the present study, several bioinformatics tools were integrated to build an in silico pipeline to evaluate the phylogenetic sensitivity of the hypervariable regions compared with the corresponding full-length sequences. Results: The correlation of seven sub-regions was inferred from the geodesic distance, a parameter that is applied to quantitatively compare the topology of different phylogenetic trees constructed using the sequences from different sub-regions. The relationship between different sub-regions based on the geodesic distance indicated that V4-V6 were the most reliable regions for representing the full-length 16S rRNA sequences in the phylogenetic analysis of most bacterial phyla, while V2 and V8 were the least reliable regions. Conclusions: Our results suggest that V4-V6 might be optimal sub-regions for the design of universal primers with superior phylogenetic resolution for bacterial phyla. A potential relationship between function and the evolution of 16S rRNA is also discussed.

In this paper, we proposes an algorithm to approximate the Geodesic distance between points p and q of sphere, through the numerical solution of initial value problem associated with the system of ordinary differential equations of the geodesics; for this an appropriate direction is obtained., En este artículo, se plantea un algoritmo para aproximar la distancia Geodésica entre los puntos p y q de la esfera, mediante la solución numérica de un problema de valor inicial asociado al sistema de ecuaciones diferenciales ordinarias de las geodésicas; para lo cual se determina una dirección apropiada.

In this paper, we proposes an algorithm to approximate the Geodesic distance between points p and q of sphere, through the numerical solution of initial value problem associated with the system of ordinary differential equations of the geodesics; for this an appropriate direction is obtained., En este artículo, se plantea un algoritmo para aproximar la distancia Geodésica entre los puntos p y q de la esfera, mediante la solución numérica de un problema de valor inicial asociado al sistema de ecuaciones diferenciales ordinarias de las geodésicas; para lo cual se determina una dirección apropiada.

Background: Prokaryotic 16S ribosomal RNA (rRNA) sequences are widely used in environmental microbiology and molecular evolution as reliable markers for the taxonomic classification and phylogenetic analysis of microbes. Restricted by current sequencing techniques, the massive sequencing of 16S rRNA gene amplicons encompassing the full length of genes is not yet feasible. Thus, the selection of the most efficient hypervariable regions for phylogenetic analysis and taxonomic classification is still debated. In the present study, several bioinformatics tools were integrated to build an in silico pipeline to evaluate the phylogenetic sensitivity of the hypervariable regions compared with the corresponding full-length sequences. Results: The correlation of seven sub-regions was inferred from the geodesic distance, a parameter that is applied to quantitatively compare the topology of different phylogenetic trees constructed using the sequences from different sub-regions. The relationship between different sub-regions based on the geodesic distance indicated that V4-V6 were the most reliable regions for representing the full-length 16S rRNA sequences in the phylogenetic analysis of most bacterial phyla, while V2 and V8 were the least reliable regions. Conclusions: Our results suggest that V4-V6 might be optimal sub-regions for the design of universal primers with superior phylogenetic resolution for bacterial phyla. A potential relationship between function and the evolution of 16S rRNA is also discussed.

Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon.

For any two points in a simple polygon P, the geodesic distance between them is the length of the shortest path contained in P that connects them. A geodesic center of a set S of sites (points) with respect to P is a point in P that minimizes the geodesic distance to its farthest site. In many realistic facility location problems, however, the facilities are constrained to lie in feasible regions. In this paper, we show how to compute the geodesic centers constrained to a set of line segments or simple polygonal regions contained in P. Our results provide substantial improvements over previous algorithms.

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611–626, 1989) showed an O(nlog n) -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem., SCOPUS: ar.j, info:eu-repo/semantics/published

Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n + m) log log n)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon., SCOPUS: cp.p, info:eu-repo/semantics/published

This work reviews and extends a family of log-determinant (log-det) divergences for symmetric positive definite (SPD) matrices and discusses their fundamental properties. We show how to use parameterized Alpha-Beta (AB) and Gamma log-det divergences to generate many well-known divergences; in particular, we consider the Stein’s loss, the S-divergence, also called Jensen-Bregman LogDet (JBLD) divergence, Logdet Zero (Bhattacharyya) divergence, Affine Invariant Riemannian Metric (AIRM), and other divergences. Moreover, we establish links and correspondences between log-det divergences and visualise them on an alpha-beta plane for various sets of parameters. We use this unifying framework to interpret and extend existing similarity measures for semidefinite covariance matrices in finite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). This paper also shows how the Alpha-Beta family of log-det divergences relates to the divergences of multivariate and multilinear normal distributions. Closed form formulas are derived for Gamma divergences of two multivariate Gaussian densities; the special cases of the Kullback-Leibler, Bhattacharyya, Rényi, and Cauchy-Schwartz divergences are discussed. Symmetrized versions of log-det divergences are also considered and briefly reviewed. Finally, a class of divergences is extended to multiway divergences for separable covariance (or precision) matrices.

This work reviews and extends a family of log-determinant (log-det) divergences for symmetric positive definite (SPD) matrices and discusses their fundamental properties. We show how to use parameterized Alpha-Beta (AB) and Gamma log-det divergences to generate many well-known divergences; in particular, we consider the Stein’s loss, the S-divergence, also called Jensen-Bregman LogDet (JBLD) divergence, Logdet Zero (Bhattacharyya) divergence, Affine Invariant Riemannian Metric (AIRM), and other divergences. Moreover, we establish links and correspondences between log-det divergences and visualise them on an alpha-beta plane for various sets of parameters. We use this unifying framework to interpret and extend existing similarity measures for semidefinite covariance matrices in finite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). This paper also shows how the Alpha-Beta family of log-det divergences relates to the divergences of multivariate and multilinear normal distributions. Closed form formulas are derived for Gamma divergences of two multivariate Gaussian densities; the special cases of the Kullback-Leibler, Bhattacharyya, Rényi, and Cauchy-Schwartz divergences are discussed. Symmetrized versions of log-det divergences are also considered and briefly reviewed. Finally, a class of divergences is extended to multiway divergences for separable covariance (or precision) matrices.

In this paper, we proposes an algorithm to approximate the Euclidean distance between points p and q of plane, by doing a search of geodesic that depart from the point p and arrive to a neighborhood of the point q . This search is done through the numerical solution of initial value problems associated with the system of ordinary differential equations of the geodesics; for this is choose a set of directions in the plane., En este artículo, se plantea un algoritmo para aproximar la distancia Euclidiana entre los puntos p y q del plano, mediante la búsqueda de geodésicas que salen del punto p y llegan a una vecindad del punto q. Esta búsqueda se hace a través de la solución numérica de problemas de valor inicial asociados a sistemas de ecuaciones diferenciales ordinarias de las geodésicas; para lo cual se elige un conjunto de direcciones en el plano.

This work reviews and extends a family of log-determinant (log-det) divergences for symmetric positive definite (SPD) matrices and discusses their fundamental properties. We show how to use parameterized Alpha-Beta (AB) and Gamma log-det divergences to generate many well-known divergences; in particular, we consider the Stein’s loss, the S-divergence, also called Jensen-Bregman LogDet (JBLD) divergence, Logdet Zero (Bhattacharyya) divergence, Affine Invariant Riemannian Metric (AIRM), and other divergences. Moreover, we establish links and correspondences between log-det divergences and visualise them on an alpha-beta plane for various sets of parameters. We use this unifying framework to interpret and extend existing similarity measures for semidefinite covariance matrices in finite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). This paper also shows how the Alpha-Beta family of log-det divergences relates to the divergences of multivariate and multilinear normal distributions. Closed form formulas are derived for Gamma divergences of two multivariate Gaussian densities; the special cases of the Kullback-Leibler, Bhattacharyya, Rényi, and Cauchy-Schwartz divergences are discussed. Symmetrized versions of log-det divergences are also considered and briefly reviewed. Finally, a class of divergences is extended to multiway divergences for separable covariance (or precision) matrices.

This work reviews and extends a family of log-determinant (log-det) divergences for symmetric positive definite (SPD) matrices and discusses their fundamental properties. We show how to use parameterized Alpha-Beta (AB) and Gamma log-det divergences to generate many well-known divergences; in particular, we consider the Stein’s loss, the S-divergence, also called Jensen-Bregman LogDet (JBLD) divergence, Logdet Zero (Bhattacharyya) divergence, Affine Invariant Riemannian Metric (AIRM), and other divergences. Moreover, we establish links and correspondences between log-det divergences and visualise them on an alpha-beta plane for various sets of parameters. We use this unifying framework to interpret and extend existing similarity measures for semidefinite covariance matrices in finite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). This paper also shows how the Alpha-Beta family of log-det divergences relates to the divergences of multivariate and multilinear normal distributions. Closed form formulas are derived for Gamma divergences of two multivariate Gaussian densities; the special cases of the Kullback-Leibler, Bhattacharyya, Rényi, and Cauchy-Schwartz divergences are discussed. Symmetrized versions of log-det divergences are also considered and briefly reviewed. Finally, a class of divergences is extended to multiway divergences for separable covariance (or precision) matrices.

This work reviews and extends a family of log-determinant (log-det) divergences for symmetric positive definite (SPD) matrices and discusses their fundamental properties. We show how to use parameterized Alpha-Beta (AB) and Gamma log-det divergences to generate many well-known divergences; in particular, we consider the Stein’s loss, the S-divergence, also called Jensen-Bregman LogDet (JBLD) divergence, Logdet Zero (Bhattacharyya) divergence, Affine Invariant Riemannian Metric (AIRM), and other divergences. Moreover, we establish links and correspondences between log-det divergences and visualise them on an alpha-beta plane for various sets of parameters. We use this unifying framework to interpret and extend existing similarity measures for semidefinite covariance matrices in finite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). This paper also shows how the Alpha-Beta family of log-det divergences relates to the divergences of multivariate and multilinear normal distributions. Closed form formulas are derived for Gamma divergences of two multivariate Gaussian densities; the special cases of the Kullback-Leibler, Bhattacharyya, Rényi, and Cauchy-Schwartz divergences are discussed. Symmetrized versions of log-det divergences are also considered and briefly reviewed. Finally, a class of divergences is extended to multiway divergences for separable covariance (or precision) matrices.

In this paper, we proposes an algorithm to approximate the Euclidean distance between points p and q of plane, by doing a search of geodesic that depart from the point p and arrive to a neighborhood of the point q . This search is done through the numerical solution of initial value problems associated with the system of ordinary differential equations of the geodesics; for this is choose a set of directions in the plane., En este artículo, se plantea un algoritmo para aproximar la distancia Euclidiana entre los puntos p y q del plano, mediante la búsqueda de geodésicas que salen del punto p y llegan a una vecindad del punto q. Esta búsqueda se hace a través de la solución numérica de problemas de valor inicial asociados a sistemas de ecuaciones diferenciales ordinarias de las geodésicas; para lo cual se elige un conjunto de direcciones en el plano.

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an O(n log n)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an O(n log n)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem., SCOPUS: cp.p, info:eu-repo/semantics/published

We introduce a framework for population analysis of white matter tracts based on diffusion-weighted images of the brain. The framework enables extraction of fibers from high angular resolution diffusion images (HARDI); clustering of the fibers based partly on prior knowledge from an atlas; representation of the fiber bundles compactly using a path following points of highest density (maximum density path; MDP); and registration of these paths together using geodesic curve matching to find local correspondences across a population. We demonstrate our method on 4-Tesla HARDI scans from 565 young adults to compute localized statistics across 50 white matter tracts based on fractional anisotropy (FA). Experimental results show increased sensitivity in the determination of genetic influences on principal fiber tracts compared to the tract-based spatial statistics (TBSS) method. Our results show that the MDP representation reveals important parts of the white matter structure and considerably reduces the dimensionality over comparable fiber matching approaches.

Kullback-Leibler information allow us to characterize a family of dis- tributions denominated Kullback-Leibler-Symmetric, which are distance functions and, under some restrictions, generate the Jensen’s equality shown by [1], in this paper denominated Jensen-Equal. On the other hand, [5] and [7] showed that graph theory gives conditions to define a new mea- surable space and, therefore, new distances, in particular, the distance characterized by [2], denominated Geodesic Distance. The interaction of these ideas allow us to define a new distribution, denominated Geodesic Distri- bution which, under graph theory as center and radius of a graph, we can to develop optimization methodologies based in probabilities of attendance. We obtain many applications and the proposal method is very adaptive. To illustrate, we apply this distribution in spatial statistics., La información de Kullback-Leibler permite caracterizar una familia de distribuciones que denominamos Kullback-Liebler-Simétricas de las cuales tenemos distribuciones que son funciones de una distancia que bajo restricciones genera la igualdad en la relación de Jensen mostrados por [1], las que denominamos Jensen-Igual. Por otra parte, [5] y [7] presentan que la teoría de grafos permite definir un espacio medible y por tanto nuevas distancias, en particular la caracterizada por [2] denominada distancia Geodésica. La interacción de las dos ideas permite inducir una distribución que denominaremos Geodésica, la cual bajo técnicas de la teoría de grafos, como el centro y el radio de un grafo, permite desarrollar metodologías de optimización en función de las probabilidades de atendimiento. Obtenemos muchas áreas de aplicación y muchas adaptaciones, en las cuales, por ejemplo, aplicamos en un problema de estadística espacial.

We introduce a framework for population analysis of white matter tracts based on diffusion-weighted images of the brain. The framework enables extraction of fibers from high angular resolution diffusion images (HARDI); clustering of the fibers based partly on prior knowledge from an atlas; representation of the fiber bundles compactly using a path following points of highest density (maximum density path; MDP); and registration of these paths together using geodesic curve matching to find local correspondences across a population. We demonstrate our method on 4-Tesla HARDI scans from 565 young adults to compute localized statistics across 50 white matter tracts based on fractional anisotropy (FA). Experimental results show increased sensitivity in the determination of genetic influences on principal fiber tracts compared to the tract-based spatial statistics (TBSS) method. Our results show that the MDP representation reveals important parts of the white matter structure and considerably reduces the dimensionality over comparable fiber matching approaches.

Kullback-Leibler information allow us to characterize a family of dis- tributions denominated Kullback-Leibler-Symmetric, which are distance functions and, under some restrictions, generate the Jensen’s equality shown by [1], in this paper denominated Jensen-Equal. On the other hand, [5] and [7] showed that graph theory gives conditions to define a new mea- surable space and, therefore, new distances, in particular, the distance characterized by [2], denominated Geodesic Distance. The interaction of these ideas allow us to define a new distribution, denominated Geodesic Distri- bution which, under graph theory as center and radius of a graph, we can to develop optimization methodologies based in probabilities of attendance. We obtain many applications and the proposal method is very adaptive. To illustrate, we apply this distribution in spatial statistics., La información de Kullback-Leibler permite caracterizar una familia de distribuciones que denominamos Kullback-Liebler-Simétricas de las cuales tenemos distribuciones que son funciones de una distancia que bajo restricciones genera la igualdad en la relación de Jensen mostrados por [1], las que denominamos Jensen-Igual. Por otra parte, [5] y [7] presentan que la teoría de grafos permite definir un espacio medible y por tanto nuevas distancias, en particular la caracterizada por [2] denominada distancia Geodésica. La interacción de las dos ideas permite inducir una distribución que denominaremos Geodésica, la cual bajo técnicas de la teoría de grafos, como el centro y el radio de un grafo, permite desarrollar metodologías de optimización en función de las probabilidades de atendimiento. Obtenemos muchas áreas de aplicación y muchas adaptaciones, en las cuales, por ejemplo, aplicamos en un problema de estadística espacial.

We present a novel way to efficiently compute Riemannian geodesic distance over a two- or three-dimensional domain. It is based on a previously presented method for computation of geodesic distances on surface meshes. Our method is adapted for rectangular grids, equipped with a variable anisotropic metric tensor. Processing and visualization of such tensor fields is common in certain applications, for instance structure tensor fields in image analysis and diffusion tensor fields in medical imaging. The included benchmark study shows that our method provides significantly better results in anisotropic regions in 2-D and 3-D and is faster than current stat-of-the- art solvers in 2-D grids. Additionally, our method is straightforward to code; the test implementation is less than 150 lines of C++ code. The paper is an extension of a previously presented conference paper and includes new sections on 3-D grids in particular.

Least square regression has been widely used in image interpolation. Some existing regression-based interpolation methods used ordinary least squares (OLS) to formulate cost functions. These methods usually have difficulties at object boundaries because OLS is sensitive to outliers. Weighted least squares (WLS) is then adopted to solve the outlier problem. Some weighting schemes have been proposed in the literature. In this paper we propose to use geodesic distance weighting in that geodesic distance can simultaneously measure both the spatial distance and color difference. Another contribution of this paper is that we propose an optimization scheme that can handle arbitrary factor interpolation. The idea is to separate the problem into two parts, an adaptive pixel correlation model and a convolution based image degradation model. Geodesic distance weighted 2D autoregressive model is used to model the pixel correlation which preserves local geometry. The convolution based image degradation model provides the flexibility to handle arbitrary interpolation factor. The entire problem is formulated as a WLS problem constrained by a linear equality. © 2013 IEEE.

Least square regression has been widely used in image interpolation. Some existing regression-based interpolation methods used ordinary least squares (OLS) to formulate cost functions. These methods usually have difficulties at object boundaries because OLS is sensitive to outliers. Weighted least squares (WLS) is then adopted to solve the outlier problem. Some weighting schemes have been proposed in the literature. In this paper we propose to use geodesic distance weighting in that geodesic distance can simultaneously measure both the spatial distance and color difference. Another contribution of this paper is that we propose an optimization scheme that can handle arbitrary factor interpolation. The idea is to separate the problem into two parts, an adaptive pixel correlation model and a convolution based image degradation model. Geodesic distance weighted 2D autoregressive model is used to model the pixel correlation which preserves local geometry. The convolution based image degradation model provides the flexibility to handle arbitrary interpolation factor. The entire problem is formulated as a WLS problem constrained by a linear equality. © 2013 IEEE.

Least square regression has been widely used in image interpolation. Some existing regression-based interpolation methods used ordinary least squares (OLS) to formulate cost functions. These methods usually have difficulties at object boundaries because OLS is sensitive to outliers. Weighted least squares (WLS) is then adopted to solve the outlier problem. Some weighting schemes have been proposed in the literature. In this paper we propose to use geodesic distance weighting in that geodesic distance can simultaneously measure both the spatial distance and color difference. Another contribution of this paper is that we propose an optimization scheme that can handle arbitrary factor interpolation. The idea is to separate the problem into two parts, an adaptive pixel correlation model and a convolution based image degradation model. Geodesic distance weighted 2D autoregressive model is used to model the pixel correlation which preserves local geometry. The convolution based image degradation model provides the flexibility to handle arbitrary interpolation factor. The entire problem is formulated as a WLS problem constrained by a linear equality. © 2013 IEEE.

In many real-world application problems, the availability of data labels for supervised learning is rather limited. Incompletely labeled datasets are common in many of the databases generated in some of the currently most active areas of research. It is often the case that a limited number of labeled cases is accompanied by a larger number of unlabeled ones. This is the setting for semi-supervised learning, in which unsupervised approaches assist the supervised problem and vice versa. A manifold learning model, namely Generative Topographic Mapping (GTM), is the basis of the methods developed in this thesis. The non-linearity of the mapping that GTM generates makes it prone to trustworthiness and continuity errors that would reduce the faithfulness of the data representation, especially for datasets of convoluted geometry. In this thesis, a variant of GTM that uses a graph approximation to the geodesic metric is first defined. This model is capable of representing data of convoluted geometries. The standard GTM is here modified to prioritize neighbourhood relationships along the generated manifold. This is accomplished by penalizing the possible divergences between the Euclidean distances from the data points to the model prototypes and the corresponding geodesic distances along the manifold. The resulting Geodesic GTM (Geo-GTM) model is shown to improve the continuity and trustworthiness of the representation generated by the model, as well as to behave robustly in the presence of noise. The thesis then leads towards the definition and development of semi-supervised versions of GTM for partially-labeled data exploration. As a first step in this direction, a two-stage clustering procedure that uses class information is presented. A class information-enriched variant of GTM, namely class-GTM, yields a first cluster description of the data. The number of clusters defined by GTM is usually large for visualization purposes and does not necessarily correspond to the over, Resum de la tesi (màxim 4000 caràcters. Si se supera aquest límit, el resum es tallarà automàticament al caràcter 4000) En muchos problemas de aplicación del mundo real, la disponibilidad de etiquetas de datos para aprendizaje supervisado es bastante limitada. La existencia de conjuntos de datos etiquetados de manera incompleta es común en muchas de las bases de datos generadas en algunas de las áreas de investigación actualmente más activas. Es frecuente que un número limitado de casos etiquetados venga acompañado de un número mucho mayor de datos no etiquetados. Éste es el contexto en el que opera el aprendizaje semi-supervisado, en el cual enfoques no-supervisados prestan ayuda a problemas supervisados y vice versa. Un modelo de aprendizaje de variaciones (manifold learning, en inglés), llamado Mapeo Topográfico Generativo (GTM, en acrónimo de su nombre en inglés), es la base de los métodos desarrollados en esta tesis. La no-linealidad del mapeo que GTM genera hace que éste sea propenso a errores de fiabilidad y continuidad, los cuales pueden reducir la fidelidad de la representación de los datos, especialmente para conjuntos de datos de geometría intrincada. En esta tesis, una extensión de GTM que utiliza una aproximación vía grafos a la métrica geodésica es definida en primer lugar. Este modelo es capaz de representar datos con geometrías intrincadas. En él, el GTM estándar es modificado para priorizar relaciones de vecindad a lo largo de la variación generada. Esto se logra penalizando las divergencias existentes entre las distancias Euclideanas de los datos a los prototipos del modelo y las correspondientes distancias geodésicas a lo largo de la variación. Se muestra que el modelo Geo-GTM resultante mejora la continuidad y fiabilidad de la representación generada y que se comporta de manera robusta en presencia de ruido. Más adelante, la tesis nos lleva a la definición y desarrollo de versiones semi-supervisadas de GTM para la exploración de conjuntos de dato, Postprint (published version)

This paper presents a novel technique for three-dimensional (3D) human motion capture using a set of two non-calibrated cameras. The user's five extremities (head, hands and feet) are extracted, labeled and tracked after silhouette segmentation. As they are the minimal number of points that can be used in order to enable whole body gestural interaction, we will henceforth refer to these features as crucial points. Features are subsequently labelled using 3D triangulation and inter-image tracking. The crucial point candidates are defined as the local maxima of the geodesic distance with respect to the center of gravity of the actor region that lie on the silhouette boundary. Due to its low computational complexity, the system can run at real-time paces on standard personal computers, with an average error rate range between 4% and 9% in realistic situations, depending on the context and segmentation quality.

This paper presents a novel technique for 2-D human motion capture using a single non calibrated camera. The user's five extremities (head, hands and feet) are extracted, labeled and tracked after silhouette segmentation. As they are the minimal number of points that can be used in order to enable whole body gestural interaction, we will henceforth refer to these features as crucial points. The crucial point candidates are defined as the local maxima of the geodesic distance with respect to the center of gravity of the actor region that lie on the silhouette boundary. In order to disambiguate the selected crucial points into head, left and right foot and left and right hand classes, we propose a Bayesian framework that combines a MAP approach weighted by a prior model and the intensities of the tracked crucial points. Due to its low computational complexity, the system can run at real-time paces on standard personal computers, with an average error rate range between 2% and 7% in realistic situations, depending on the context and segmentation quality.

A new method for obtaining the optimal path to robot navigation in 2-D environments is presented in this paper. To obtain the optimal path we use mathematical morphology in binary worlds and the geodesic distance. The navigation algorithm is based on the search for a path of minimum cost by using the wave-front of the geodesic distance of the mathematical morphology. The optimal path will be the one that minimize the direction changes of the robot. The algorithm of optimal path will be applied in several and complex 2-D environments.