BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vitaliy Kurlin

Vitaliy Kurlin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Geometrymath.MGData Structures and Algorithmsmath.GTComputational ComplexityComputer Visioncond-mat.mtrl-scimath.AT

Catalog footprint

What is connected

17works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2025arXiv

Computing the bridge length: the key ingredient in a continuous isometry classification of periodic point sets

The fundamental model of any periodic crystal is a periodic set of points at all atomic centres. Since crystal structures are determined in a rigid form, their strongest equivalence is rigid motion (composition of translations and rotations) or isometry (also including reflections). The recent classification of periodic point sets under rigid motion used a complete invariant isoset whose size essentially depends on the bridge length, defined as the minimum `jump' that suffices to connect any points in the given set. We propose a practical algorithm to compute the bridge length of any periodic point set given by a motif of points in a periodically translated unit cell. The algorithm has been tested on a large crystal dataset and is required for an efficient continuous classification of all periodic crystals. The exact computation of the bridge length is a key step to realising the inverse design of materials from new invariant values.

0 citations0 reviewsNo code linkedOpen access
preprint2025arXiv

Pointwise Distance Distributions for detecting near-duplicates in large materials databases

Many real objects are modeled as discrete sets of points, such as corners or other salient features. For our main applications in chemistry, points represent atomic centers in a molecule or a solid material. We study the problem of classifying discrete (finite and periodic) sets of unordered points under isometry, which is any transformation preserving distances in a metric space. Experimental noise motivates the new practical requirement to make such invariants Lipschitz continuous so that perturbing every point in its epsilon-neighborhood changes the invariant up to a constant multiple of epsilon in a suitable distance satisfying all metric axioms. Since the given points are unordered, the key challenge is to compute all invariants and metrics in a near-linear time of the input size. We define the Pointwise Distance Distribution (PDD) for any discrete set and prove, in addition to the properties above, the completeness of PDD for all periodic sets in general position. The PDD can compare nearly 2 million crystals from the world's five largest databases within 2 hours on a modest desktop computer. The impact is upholding data integrity in crystallography because the PDD will not allow anyone to claim a `new' material as a noisy disguise of a known crystal.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Density functions of periodic sequences of continuous events

Periodic Geometry studies isometry invariants of periodic point sets that are also continuous under perturbations. The motivations come from periodic crystals whose structures are determined in a rigid form but any minimal cells can discontinuously change due to small noise in measurements. For any integer k>=0, the density function of a periodic set S was previously defined as the fractional volume of all k-fold intersections (within a minimal cell) of balls that have a variable radius t and centers at all points of S. This paper introduces the density functions for periodic sets of points with different initial radii motivated by atomic radii of chemical elements and by continuous events occupying disjoint intervals in time series. The contributions are explicit descriptions of the densities for periodic sequences of intervals. The new densities are strictly stronger and distinguish periodic sequences that have identical densities in the case of zero radii.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A complete isometry classification of 3-dimensional lattices

A periodic lattice in Euclidean 3-space is the infinite set of all integer linear combinations of basis vectors. Any lattice can be generated by infinitely many different bases. This ambiguity was only partially resolved, but standard reductions remained discontinuous under perturbations modelling crystal vibrations. This paper completes a continuous classification of 3-dimensional lattices up to Euclidean isometry (or congruence) and similarity (with uniform scaling).The new homogeneous invariants are uniquely ordered square roots of scalar products of four superbase vectors whose sum is zero and all pairwise angles are non-acute. These root invariants continuously change under perturbations of basis vectors. The geometric methods extend the work of Delone, Conway and Sloane.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006

This paper is motivated by the k-nearest neighbors search: given an arbitrary metric space, and its finite subsets (a reference set R and a query set Q), design a fast algorithm to find all k-nearest neighbors in R for every point q in Q. In 2006, Beygelzimer, Kakade, and Langford introduced cover trees to justify a near-linear time complexity for the neighbor search in the sizes of Q,R. Section 5.3 of Curtin's PhD (2015) pointed out that the proof of this result was wrong. The key step in the original proof attempted to show that the number of iterations can be estimated by multiplying the length of the longest root-to-leaf path in a cover tree by a constant factor. However, this estimate can miss many potential nodes in several branches of a cover tree, that should be considered during the neighbor search. The same argument was unfortunately repeated in several subsequent papers using cover trees from 2006. This paper explicitly constructs challenging datasets that provide counterexamples to the past proofs of time complexity for the cover tree construction, the k-nearest neighbor search presented at ICML 2006, and the dual-tree search algorithm published in NIPS 2009. The corrected near-linear time complexities with extra parameters are proved in another forthcoming paper by using a new compressed cover tree simplifying the original tree structure.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Density functions of periodic sequences

Periodic point sets model all solid crystalline materials whose structures are determined in a rigid form and should be studied up to rigid motion or isometry preserving inter-point distances. In 2021 H.Edelsbrunner et al. introduced an infinite sequence of density functions that are continuous isometry invariants of periodic point sets. These density functions turned out to be highly non-trivial even in dimension 1 for periodic sequences of points in the line. This paper fully describes the density functions of any periodic sequence and their symmetry properties. The explicit description theoretically confirms coincidences of density functions that were previously computed only through finite samples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Exactly computable and continuous metrics on isometry classes of finite and 1-periodic sequences

The inevitable noise in real measurements motivates the problem to continuously quantify the similarity between rigid objects such as periodic time series and proteins given by ordered points and considered up to isometry maintaining inter-point distances. The past work produced many Hausdorff-like distances that have slow or approximate algorithms due to minimizations over infinitely many isometries. For finite and 1-periodic sequences under isometry in any high-dimensional Euclidean space, we introduce continuous metrics with faster algorithms. The key novelty in the periodic case is the continuity of new metrics under perturbations that change the minimum period.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Geographic-style maps for 2-dimensional lattices

This paper develops geographic-style maps containing 2D lattices in all known crystals parameterised by recent complete invariants. Motivated by rigid crystal structures, lattices are considered up to rigid motion and uniform scaling. The resulting space of 2D lattices is a square with identified edges or a sphere without one point. The new continuous maps show all Bravais classes as low-dimensional subspaces, visualise hundreds of thousands of real crystal lattices from the Cambridge Structural Database, and motivate the development of continuous and invariant-based crystallography.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Mathematics of 2-dimensional lattices

A periodic lattice in Euclidean space is the infinite set of all integer linear combinations of basis vectors. Any lattice can be generated by infinitely many different bases. This ambiguity was only partially resolved, but standard reductions remained discontinuous under perturbations modelling crystal vibrations. This paper completes a continuous classification of 2-dimensional lattices up to Euclidean isometry (or congruence), rigid motion (without reflections), and similarity (with uniform scaling). The new homogeneous invariants allow easily computable metrics on lattices considered up to the equivalences above. The metrics up to rigid motion are especially non-trivial and settle all remaining questions on (dis)continuity of lattice bases. These metrics lead to real-valued chiral distances that continuously measure a lattice deviation from a higher-symmetry neighbour.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Paired compressed cover trees guarantee a near linear parametrized complexity for all $k$-nearest neighbors search in an arbitrary metric space

This paper studies the important problem of finding all $k$-nearest neighbors to points of a query set $Q$ in another reference set $R$ within any metric space. Our previous work defined compressed cover trees and corrected the key arguments in several past papers for challenging datasets. In 2009 Ram, Lee, March, and Gray attempted to improve the time complexity by using pairs of cover trees on the query and reference sets. In 2015 Curtin with the above co-authors used extra parameters to finally prove a time complexity for $k=1$. The current work fills all previous gaps and improves the nearest neighbor search based on pairs of new compressed cover trees. The novel imbalance parameter of paired trees allowed us to prove a better time complexity for any number of neighbors $k\geq 1$.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Skeletonisation Algorithms with Theoretical Guarantees for Unorganised Point Clouds with High Levels of Noise

Data Science aims to extract meaningful knowledge from unorganised data. Real datasets usually come in the form of a cloud of points with only pairwise distances. Numerous applications require to visualise an overall shape of a noisy cloud of points sampled from a non-linear object that is more complicated than a union of disjoint clusters. The skeletonisation problem in its hardest form is to find a 1-dimensional skeleton that correctly represents a shape of the cloud. This paper compares several algorithms that solve the above skeletonisation problem for any point cloud and guarantee a successful reconstruction. For example, given a highly noisy point sample of an unknown underlying graph, a reconstructed skeleton should be geometrically close and homotopy equivalent to (has the same number of independent cycles as) the underlying graph. One of these algorithm produces a Homologically Persistent Skeleton (HoPeS) for any cloud without extra parameters. This universal skeleton contains sub-graphs that provably represent the 1-dimensional shape of the cloud at any scale. Other subgraphs of HoPeS reconstruct an unknown graph from its noisy point sample with a correct homotopy type and within a small offset of the sample. The extensive experiments on synthetic and real data reveal for the first time the maximum level of noise that allows successful graph reconstructions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A fast approximate skeleton with guarantees for any cloud of points in a Euclidean space

The tree reconstruction problem is to find an embedded straight-line tree that approximates a given cloud of unorganized points in $\mathbb{R}^m$ up to a certain error. A practical solution to this problem will accelerate a discovery of new colloidal products with desired physical properties such as viscosity. We define the Approximate Skeleton of any finite point cloud $C$ in a Euclidean space with theoretical guarantees. The Approximate Skeleton ASk$(C)$ always belongs to a given offset of $C$, i.e. the maximum distance from $C$ to ASk$(C)$ can be a given maximum error. The number of vertices in the Approximate Skeleton is close to the minimum number in an optimal tree by factor 2. The new Approximate Skeleton of any unorganized point cloud $C$ is computed in a near linear time in the number of points in $C$. Finally, the Approximate Skeleton outperforms past skeletonization algorithms on the size and accuracy of reconstruction for a large dataset of real micelles and random clouds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Encoding and Topological Computation on Textiles

A textile structure is a periodic arrangement of threads in the thickened plane. A topological classification of textile structures is harder than for classical knots and links that are non-periodic and restricted to a bounded region. The first important problem is to encode all textile structures in a simple combinatorial way. This paper extends the notion of the Gauss code in classical knot theory, providing a tool for topological computation on these structures. As a first application, we present a linear time algorithm for determining whether a code represents a textile in the physical sense. This algorithm, along with invariants of textile structures, allowed us for the first time to classify all oriented textile structures woven from a single component up to complexity five.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The mergegram of a dendrogram and its stability

This paper extends the key concept of persistence within Topological Data Analysis (TDA) in a new direction. TDA quantifies topological shapes hidden in unorganized data such as clouds of unordered points. In the 0-dimensional case the distance-based persistence is determined by a single-linkage (SL) clustering of a finite set in a metric space. Equivalently, the 0D persistence captures only edge-lengths of a Minimum Spanning Tree (MST). Both SL dendrogram and MST are unstable under perturbations of points. We define the new stable-under-noise mergegram, which outperforms previous isometry invariants on a classification of point clouds by PersLay.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A fast and robust algorithm to count topologically persistent holes in noisy clouds

Preprocessing a 2D image often produces a noisy cloud of interest points. We study the problem of counting holes in unorganized clouds in the plane. The holes in a given cloud are quantified by the topological persistence of their boundary contours when the cloud is analyzed at all possible scales. We design the algorithm to count holes that are most persistent in the filtration of offsets (neighborhoods) around given points. The input is a cloud of $n$ points in the plane without any user-defined parameters. The algorithm has $O(n\log n)$ time and $O(n)$ space. The output is the array (number of holes, relative persistence in the filtration). We prove theoretical guarantees when the algorithm finds the correct number of holes (components in the complement) of an unknown shape approximated by a cloud.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

All 2-dimensional links in 4-space live inside a universal 3-dimensional polyhedron

The hexabasic book is the cone of the 1-dimensional skeleton of the union of two tetrahedra glued along a common face. The universal 3-dimensional polyhedron UP is the product of a segment and the hexabasic book. We show that any 2-dimensional link in 4-space is isotopic to a surface in UP. The proof is based on a representation of surfaces in 4-space by marked graphs, links with double intersections in 3-space. We construct a finitely presented semigroup whose central elements uniquely encode all isotopy classes of 2-dimensional links.

0 citations0 reviewsNo code linkedOpen access