We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary...We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.展开更多
A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multipl...A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multiplication in recursive computation is replaced by shifting. Complexity of the algorithm is studied. A factor η is introduced and presented. When the ratio of multiplier's period Tm to adder's period Ta is greater than the factor η (i.e.Tm / Ta >η), the new algorithm is faster than FFT. The necessary condition and error of the algorithm are studied. The signal-to-noise ratio for different length N is presented. A high accuracy scheme is proposed for improving the SNR about 20 -30dB.展开更多
In this paper,we consider the knot placement problem in B-spline curve approximation.A novel two-stage framework is proposed for addressing this problem.In the first step,the l_(∞,1)-norm model is introduced for the ...In this paper,we consider the knot placement problem in B-spline curve approximation.A novel two-stage framework is proposed for addressing this problem.In the first step,the l_(∞,1)-norm model is introduced for the sparse selection of candidate knots from an initial knot vector.By this step,the knot number is determined.In the second step,knot positions are formulated into a nonlinear optimization problem and optimized by a global optimization algorithm—the differential evolution algorithm(DE).The candidate knots selected in the first step are served for initial values of the DE algorithm.Since the candidate knots provide a good guess of knot positions,the DE algorithm can quickly converge.One advantage of the proposed algorithm is that the knot number and knot positions are determined automatically.Compared with the current existing algorithms,the proposed algorithm finds approximations with smaller fitting error when the knot number is fixed in advance.Furthermore,the proposed algorithm is robust to noisy data and can handle with few data points.We illustrate with some examples and applications.展开更多
针对现有最大供电能力(TSC)模型无法反映变电站低压侧接线形式不同以及主变N-1后站内优先转带的问题,提出一种基于N-1仿真逼近的计及变电站低压侧接线的配电网TSC算法。根据我国高压配电变电站10 k V侧典型低压侧接线建立配电网算例,研...针对现有最大供电能力(TSC)模型无法反映变电站低压侧接线形式不同以及主变N-1后站内优先转带的问题,提出一种基于N-1仿真逼近的计及变电站低压侧接线的配电网TSC算法。根据我国高压配电变电站10 k V侧典型低压侧接线建立配电网算例,研究TSC随低压侧接线形式不同的变化规律以及低压侧接线对TSC的影响机理。仿真结果表明所提方法所得TSC更为精确。展开更多
L-band digital aeronautical communication system 1(L-DACS1) is a promising candidate data-link for future air-ground communication, but it is severely interfered by the pulse pairs(PPs) generated by distance measure e...L-band digital aeronautical communication system 1(L-DACS1) is a promising candidate data-link for future air-ground communication, but it is severely interfered by the pulse pairs(PPs) generated by distance measure equipment. A novel PP mitigation approach is proposed in this paper. Firstly, a deformed PP detection(DPPD) method that combines a filter bank, correlation detection, and rescanning is proposed to detect the deformed PPs(DPPs) which are caused by multiple filters in the receiver. Secondly, a finite impulse response(FIR) model is used to approximate the overall characteristic of filters, and then the waveform of DPP can be acquired by the original waveform of PP and the FIR model. Finally, sparse representation is used to estimate the position and amplitude of each DPP, and then reconstruct each DPP. The reconstructed DPPs will be subtracted from the contaminated signal to mitigate interference. Numerical experiments show that the bit error rate performance of our approach is about 5 dB better than that of recent works and is closer to interference-free environment.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11861075 and 12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE160006)+2 种基金Key Project of Yunnan Provincial Science and Technology Department and Yunnan University(No.2018FY001014)Program for Innovative Research Team(in Science and Technology)in Universities of Yunnan Province(No.C176240111009)Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province.Su-Ding Liu is also supported by the Graduate Research and Innovation Project of Yunnan University(No.2020Z66).
文摘We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.
文摘A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multiplication in recursive computation is replaced by shifting. Complexity of the algorithm is studied. A factor η is introduced and presented. When the ratio of multiplier's period Tm to adder's period Ta is greater than the factor η (i.e.Tm / Ta >η), the new algorithm is faster than FFT. The necessary condition and error of the algorithm are studied. The signal-to-noise ratio for different length N is presented. A high accuracy scheme is proposed for improving the SNR about 20 -30dB.
基金supported by the National Natural Science Foundation of China(Nos.11871447,11801393)the Natural Science Foundation of Jiangsu Province(No.BK20180831).
文摘In this paper,we consider the knot placement problem in B-spline curve approximation.A novel two-stage framework is proposed for addressing this problem.In the first step,the l_(∞,1)-norm model is introduced for the sparse selection of candidate knots from an initial knot vector.By this step,the knot number is determined.In the second step,knot positions are formulated into a nonlinear optimization problem and optimized by a global optimization algorithm—the differential evolution algorithm(DE).The candidate knots selected in the first step are served for initial values of the DE algorithm.Since the candidate knots provide a good guess of knot positions,the DE algorithm can quickly converge.One advantage of the proposed algorithm is that the knot number and knot positions are determined automatically.Compared with the current existing algorithms,the proposed algorithm finds approximations with smaller fitting error when the knot number is fixed in advance.Furthermore,the proposed algorithm is robust to noisy data and can handle with few data points.We illustrate with some examples and applications.
文摘针对现有最大供电能力(TSC)模型无法反映变电站低压侧接线形式不同以及主变N-1后站内优先转带的问题,提出一种基于N-1仿真逼近的计及变电站低压侧接线的配电网TSC算法。根据我国高压配电变电站10 k V侧典型低压侧接线建立配电网算例,研究TSC随低压侧接线形式不同的变化规律以及低压侧接线对TSC的影响机理。仿真结果表明所提方法所得TSC更为精确。
基金supported in part by the National Natural Science Foundation (Nos. U1533107 and U1433105)the Civil Aviation Science and Technology Innovation Foundation (No. MHRD20130217)the Fundamental Research Funds for the Central Universities of CAUC (No. 3122016D003)
文摘L-band digital aeronautical communication system 1(L-DACS1) is a promising candidate data-link for future air-ground communication, but it is severely interfered by the pulse pairs(PPs) generated by distance measure equipment. A novel PP mitigation approach is proposed in this paper. Firstly, a deformed PP detection(DPPD) method that combines a filter bank, correlation detection, and rescanning is proposed to detect the deformed PPs(DPPs) which are caused by multiple filters in the receiver. Secondly, a finite impulse response(FIR) model is used to approximate the overall characteristic of filters, and then the waveform of DPP can be acquired by the original waveform of PP and the FIR model. Finally, sparse representation is used to estimate the position and amplitude of each DPP, and then reconstruct each DPP. The reconstructed DPPs will be subtracted from the contaminated signal to mitigate interference. Numerical experiments show that the bit error rate performance of our approach is about 5 dB better than that of recent works and is closer to interference-free environment.
