# Davood Bakhshesh

Hi, and welcome to my homepage.

I am a PhD student, under the supervision
of Dr. Mohammad Farshi, and a member of
Combinatorial & Geometric Algorithms Lab., at the
Department of Computer Science of the
Yazd University, Yazd, Iran.

## Education:

- M.Sc. in Computer Science, Sharif University of Technology, Tehran, Iran [Sept 2007-Feb 2010].
- B.Sc. in Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran [Sept 2003-Sept 2007].

## Research Interests:

Computational Geometry, Geometric Algorithms and Computer Aided Geometric Design.

## Currently under review

### 2017

• #### 2-domination number of generalized Petersen graphs

, , and .
Submitted to Proceedings - Mathematical Sciences.

## Journal papers

### 2017

• #### Angle-constrained spanners with angle at least $\pi/3$

Abstract: Let $S$ be a set of $n$ points in $\mathbb{R}^d$ and let $t \geq 1$ be a real number. A geometric graph $G$ with vertex set $S$ is called a \it $t$-spanner for $S$ if for each two points $p$ and $q$ in $S$, there exists a path $Q$ in $G$ between $p$ and $q$ whose length is at most $t$ times $|pq|$, the Euclidean distance between $p$ and $q$. The geometric graph $G$ with vertex set $S$ is called a \it $\theta$-angle-constrained $t$-spanner if $G$ is a $t$-spanner of $S$ and any two edges ${p,q}$ and ${p,r}$ in $G$ make an angle of at least $\theta$. In this paper, we show that there is a point set $P$ in the plane such that for every $\theta>\pi/3$, there is no $\theta$-angle-constrained $t$-spanner on $P$. Moreover, we show that for $\theta=\pi/3$ and every $t<2/\sqrt{3}$, there is no $\theta$-angle-constrained $t$-spanner on $P$. This solves an open problem posed by Paz Carmi and Michiel Smid (Journal of Computational Geometry, 3(1):196--221, 2012)
and .
Information Processing Letters, 120:44 – 46, 2017.
@article{Bakhshesh201744,
title={Angle-constrained spanners with angle at least $\pi/3$},
journal={Information Processing Letters},
year={2017},
volume={120},
pages={44 - 46},
issn={0020-0190},
doi={http://dx.doi.org/10.1016/j.ipl.2017.01.002},
url={//www.sciencedirect.com/science/article/pii/S0020019017300029}
}

• #### Complexity results for $k$-domination and $\alpha$-domination problems and their variants

Abstract: Let $G=(V, E)$ be a simple and undirected graph. For some integer $k\geq 1$, a set $D\subseteq V$ is said to be a $k$-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $k$ neighbors in $D$. Furthermore, for some real number $\alpha$ with $0<\alpha\leq1$, a set $D\subseteq V$ is called an $\alpha$-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $\alpha\times d_v$ neighbors in $D$, where $d_v$ is the degree of $v$ in $G$. The cardinality of a minimum $k$-dominating set and a minimum $\alpha$-dominating set in $G$ is said to be the $k$-domination number and the $\alpha$-domination number of $G$, respectively. In this paper, we present some approximability and inapproximability results on the problem of finding of $k$-domination number and $\alpha$-domination number of some classes of graphs. Moreover, we introduce a generalization of $\alpha$-dominating set which we call $f$-dominating set. Given a function $f:\mathbb{N}\rightarrow \mathbb{R}$, where $\mathbb{N}={1,2,3,\ldots,}$, a set $D\subseteq V$ is said to be an $f$-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $f(d_v)$ neighbors in $D$. We prove NP-hardness of the problem of finding of a minimum $f$-dominating set in $G$, for a large family of functions $f$.
, , and .
Accepted to Ars Combinatoria.
@article{Bakhshesh2017ars,
title={Complexity results for {$k$}-domination and {$\alpha$}-domination problems and their variants},
journal={Ars Combinatoria},
year={2017}
}

• #### Improving space and time complexity of the gap-greedy spanner algorithm

Abstract: Let $S$ be a set of $n$ points in $\mathbb{R}^d$ and $G$ be a geometric graph with vertex set $S$. For a fixed real number $t \geq 1$, $G$ is called a $t$-spanner of $S$ if, for all pairs of vertices $u, v \in S$, the shortest path in $G$ between $u$ and $v$ is no longer than $t|uv|$, where $| uv|$ is the Euclidean distance between $u$ and $v$. One of the interesting geometric spanner is \it the gap-greedy spanner. It is well known that the edge count and the maximal degree of the gap-greedy spanner are asymptotically optimal and its total weight is $O(\log n)$ times the weight of the minimum spanning tree for the same vertices. To the best of our knowledge, there is one algorithm, denoted by \it gap-greedy algorithm, to construct the gap-greedy spanner that takes $O(n^3)$ time and $O(n^2)$ space. Note that there is an approximation version of the gap-greedy algorithm, denoted by \it modified gap-greedy algorithm, that constructs a geometric graph in $O(n\log ^2n)$ time and $O(n\log ^2n)$ space keeping all geometric properties the same as the gap-greedy spanner, but the generated graph is not the same as the gap-greedy spanner. In this paper, we present an algorithm to construct the gap-greedy spanner that takes $O(n^2)$ time and $O(n^2)$ space, and another variant of this algorithm that takes $O(n^3)$ time and $O(n)$ space. We also improve the (theoretical) dilation of the gap-greedy spanner. Moreover, we present some other $O(n^3)$ time algorithms to construct the gap-greedy spanner and compare their time complexity with the gap-greedy algorithm in practice. Furthermore, we experimentally compare the running time and some geometric properties of the gap-greedy spanner with the \it greedy spanner as a high quality spanner. We hoped that we can find some point sets in the plane such that the geometric properties of the gap-greedy spanner and the greedy spanner of the point sets are almost the same and the running time of computing the gap-greedy spanner is faster than the greedy spanner, but the experiments show that this is not correct.
and .
Accepted to CSI Journal on Computer Science and Engineering.
@article{Bakhshesh2017CSIGap,
title={Improving space and time complexity of the gap-greedy spanner algorithm},
journal={CSI Journal on Computer Science and Engineering},
year={2017}
}


### 2015

• #### On the effect of inducted negative correlation rate for beta acceptance–rejection algorithms

Abstract: One of the variance reduction methods in simulation experiments is negative correlation induction, and in particular the use of the antithetic variates. The simultaneous use of antithetic variates and an acceptance–rejection method has been studied in some papers, where the inducted negative correlation has been calculated. In this study, the factors affecting the inducted negative correlation rate are addressed. To do this, the beta distribution is first selected to generate negatively correlated random variates using the acceptance–rejection method. The effects of both the efficiency of the acceptance–rejection method and the initial negative correlation rate on the inducted negative correlation are explored. Results show that both factors have significant effects; therefore, a combination of both can lead to algorithms better able to generate negative correlations.
, , , and .
Accepted to Communications in Statistics - Simulation and Computation.
@article{Moheghi2015,
author={Hamidreza Moheghi and Seyed Taghi Akhavan Niaki and Behrang Bootaki and Davood Bakhshesh},
title={On the effect of inducted negative correlation rate for beta acceptance–rejection algorithms},
journal={Communications in Statistics - Simulation and Computation},
year={2015},
doi={10.1080/03610918.2015.1039128},
eprint={http://dx.doi.org/10.1080/03610918.2015.1039128},
url={http://dx.doi.org/10.1080/03610918.2015.1039128}
}

• #### Approximating of conic sections by DP curves with endpoint interpolation

Abstract: Conic sections have many applications in industrial design, however, they cannot be exactly represented in polynomial form. Hence approximating conic sections with polynomials is a challenging problem. In this paper, we use the monomial form of Delgado and Peña (DP) curves and present a matrix representation for them. Using the matrix form and the least squares method, we propose a simple and efficient algorithm for approximating conic sections by DP curves of arbitrary degree with endpoint interpolation. Finally, we test and compare the proposed algorithm on some numerical examples which validates and confirms efficiency of it.
and .
International Journal of Computer Mathematics, 92(1):1–14, 2015.
@article{doi:10.1080/00207160.2014.889293,
author={Davood Bakhshesh and Mansoor Davoodi},
title={Approximating of conic sections by {DP} curves with endpoint interpolation},
journal={International Journal of Computer Mathematics},
year={2015},
volume={92},
number={1},
pages={1-14},
doi={10.1080/00207160.2014.889293},
eprint={http://dx.doi.org/10.1080/00207160.2014.889293},
url={http://dx.doi.org/10.1080/00207160.2014.889293}
}


### 2013

• #### A new univariate basis for curve construction and its multi-degree reduction

Abstract: In this paper, we employ monomial matrices to determine the transformations between Chebyshev and our proposed bases, as well as, the matrices of multi-degree elevation and multi-degree reduction of Chebyshev polynomials. As a result, it will present a simple and efficient method for multi-degree elevation and optimal multi-degree reduction for the new polynomial curves with respect to the weighted $L_2$-norm for the interval $[0, 1]$, using the weight function $w(t) =1/\sqrt{4t-4t^2}$. The error of the degree reduction scheme will be used to evaluate the multi-degree reduction with endpoint interpolations.
and .
@article{Dejdumrong:2013:1936-6612:1495,
author={Dejdumrong, Natasha and Bakhshesh, Davood},
title={A New Univariate Basis for Curve Construction and Its Multi-Degree Reduction},
year={2013},
volume={19},
number={5},
pages={1495-1499},
issn={1936-6612},
doi={doi:10.1166/asl.2013.4463},
url={http://www.ingentaconnect.com/content/asp/asl/2013/00000019/00000005/art00055}
}


## Conference papers

### 2016

• #### Some properties of continuous Yao graph

and .
In Proceedings of the 1st Topics in Theoretical Computer Science, (TTCS 2015), Lecture Notes in Computer Science, pages 44–55, Cham, 2016.
@inproceedings{Bakhshesh2016,
title={Some Properties of Continuous {Y}ao Graph},
booktitle={Proceedings of the 1st Topics in Theoretical Computer Science, (TTCS 2015)},
year={2016},
series={Lecture Notes in Computer Science},
pages={44--55},
isbn={978-3-319-28678-5},
doi={10.1007/978-3-319-28678-5_4},
url={http://dx.doi.org/10.1007/978-3-319-28678-5_4}
}

• #### Geometric spanners merging and its applications

and .
In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), Simon Fraser University, Vancouver, Canada, 2016.
@inproceedings{Bakhshesh2016Merging,
title={Geometric Spanners Merging and its Applications},
booktitle={Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)},
year={2016},
url={http://www.sfu.ca/~shermer/CCCG2016/}
}

• #### The firm gap property and its applications

and .
In Proceedings of the47th Annual Iranian Mathematics Conference (AIMC 47), Kharazmi University, Karaj, Iran., 2016.
@inproceedings{Bakhshesh2016firm,
title={The Firm Gap Property and Its Applications},
booktitle={Proceedings of the47th Annual Iranian Mathematics Conference (AIMC 47)},
year={2016},
url={http://aimc47.khu.ac.ir/}
}


### 2015

• #### A generalization of $\alpha$-dominating set and its complexity

, , and .
In Proceedings of the 46th Annual Iranian Mathematics Conference (AIMC 46), Yazd University, Yazd, Iran, 2015.
@inproceedings{Bakhshesh2015alpha,
title={A generalization of {$\alpha$}-dominating set and its complexity},
booktitle={Proceedings of the 46th Annual Iranian Mathematics Conference (AIMC 46)},
year={2015},
url={http://confs.yazd.ac.ir/AIMC46/}
}


### 2011

• #### A combination method for image encryption based on hyper-chaos functions and evolutionary operators

and .
In Proceedings of the 8th International ISC Conference on Information Security and Cryptology (ISCISC 2011),, Ferdowsi University of Mashhad, Mashhad, Iran, 2011.
@inproceedings{Bakhsheshhamid,
author={Esfahani, Seyyed Abdolhamid and Bakhshesh, Davood},
title={A combination method for image encryption based on hyper-chaos functions and evolutionary operators},
booktitle={Proceedings of the 8th International ISC Conference on Information Security and Cryptology (ISCISC 2011),},
year={2011},