Extension of one-dimensional proximity regions to higher dimensions

DOI10.1016/J.COMGEO.2010.05.002MaRDI QIDQ991185zbMATH OpenOpenAlexFDO

Authors Elvan Ceyhan

Publication date 2 September 2010

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.1306

zbMATH Keywords

numerical examplesrandom graphdomination numberDelaunay triangulationproximity maptriangle centerrelative densityproximity catch digraphclass cover catch digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: Proximity maps and regions are defined based on the relative allocation of points from two or more classes in an area of interest and are used to construct random graphs called proximity catch digraphs (PCDs) which have applications in various fields. The simplest of such maps is the spherical proximity map which maps a point from the class of interest to a disk centered at the same point with radius being the distance to the closest point from the other class in the region. The spherical proximity map gave rise to class cover catch digraph (CCCD) which was applied to pattern classification. Furthermore for uniform data on the real line, the exact and asymptotic distribution of the domination number of CCCDs were analytically available. In this article, we determine some appealing properties of the spherical proximity map in compact intervals on the real line and use these properties as a guideline for defining new proximity maps in higher dimensions. Delaunay triangulation is used to partition the region of interest in higher dimensions. Furthermore, we introduce the auxiliary tools used for the construction of the new proximity maps, as well as some related concepts that will be used in the investigation and comparison of them and the resulting graphs. We characterize the geometry invariance of PCDs for uniform data. We also provide some newly defined proximity maps in higher dimensions as illustrative examples.

Recommendations

• An investigation of new graph invariants related to the domination number of random proximity catch digraphs
• The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association
• Relative density of the random \(R\)-factor proximity catch digraph for testing spatial patterns of segregation and association
• A new family of proximity graphs: class cover catch digraphs
• The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data

Cites work

• scientific article; zbMATH DE number 3551712 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 1455125 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A new family of proximity graphs: class cover catch digraphs
• A new family of random graphs for testing spatial segregation
• Characterizing the scale dimension of a high-dimensional classification problem
• Class cover catch digraphs for latent class discovery in gene expression monitoring by DNA microarrays
• Classification using class cover catch digraphs
• Inequalities for minimal covering sets in set systems of given rank
• Interval digraphs: An analogue of interval graphs
• On nearest-neighbor graphs
• On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs
• On the distribution of the domination number for random class cover catch digraphs
• Relative density of the random \(R\)-factor proximity catch digraph for testing spatial patterns of segregation and association
• Spatial clustering tests based on the domination number of a new random digraph family
• The relative neighbourhood graph of a finite planar set
• The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association

Cited in

(5)

• Lifting the regionally proximal relation and characterizations of distal extensions
• Law of large numbers for a two-dimensional class cover problem
• Comparison of relative density of two random geometric digraph families in testing spatial clustering
• Edge density of new graph types based on a random digraph family
• Classification using proximity catch digraphs

This page was built for publication: Extension of one-dimensional proximity regions to higher dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991185)