Extension of one-dimensional proximity regions to higher dimensions

DOI10.1016/J.COMGEO.2010.05.002zbMATH Open1229.65046arXiv0902.1306OpenAlexW2149937748MaRDI QIDQ991185FDOQ991185

Authors: Elvan Ceyhan 

Publication date: 2 September 2010

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)