Search

In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that O (f (k) log O (1) n) space is enough, where f is an arbitrary computable function depending only on the parameter k. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover or Maximum Matching parameterized by the size k of the solution we are seeking. Chitnis et al. (SODA'16) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require Ω (n) bits of storage for any streaming algorithm; e.g. Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion or the more general F -Subgraph Deletion when parameterized by solution size k. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models. Surprisingly, the consideration of vertex cover size K in the different models leads to a classification of positive and negative results for problems like F -Subgraph Deletion and F -Minor Deletion. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the number of triangles in a graph using only polylogarithmic queries when the number of triangles on any edge in the graph is polylogarithmically bounded. Our query oracle Tripartite Independent Set (TIS) takes three disjoint sets of vertices A, B and C as inputs, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of group queries (Ron and Tsur ACM Trans. Comput. Theory 8(4), 15, 2016; Dell and Lapinskas 2018) and in particular is inspired by the Bipartite Independent Set (BIS) query oracle of Beame et al. (2018). We extend the algorithmic framework of Beame et al., with TIS replacing BIS, for approximately counting triangles in graphs. [ABSTRACT FROM AUTHOR]

The grid obstacle representation , or alternately, ℓ 1 -obstacle representation of a graph G = (V , E) is an injective function f : V → Z 2 and a set of point obstacles O on the grid points of Z 2 (where no vertex of V has been mapped) such that u v is an edge in G if and only if there exists a Manhattan path between f (u) and f (v) in Z 2 avoiding the obstacles of O and points in f (V). This work shows that planar graphs admit such a representation while there exist some non-planar graphs that do not admit such a representation. Moreover, we show that every graph admits a grid obstacle representation in Z 3. We also show NP-hardness result for the point set embeddability of an ℓ 1 -obstacle representation. [ABSTRACT FROM AUTHOR]

A set D ⊆ V is called a k - tuple dominating set of a graph G = ( V , E ) if | N G [ v ] ∩ D | ≥ k for all v ∈ V , where N G [ v ] denotes the closed neighborhood of v . A set D ⊆ V is called a liar’s dominating set of a graph G = ( V , E ) if (i) | N G [ v ] ∩ D | ≥ 2 for all v ∈ V and (ii) for every pair of distinct vertices u , v ∈ V , | ( N G [ u ] ∪ N G [ v ] ) ∩ D | ≥ 3 . Given a graph G , the decision versions of k - Tuple Domination Problem and the Liar’s Domination Problem are to check whether there exist a k -tuple dominating set and a liar’s dominating set of G of a given cardinality, respectively. These two problems are known to be NP -complete (Liao and Chang, 2003; Slater, 2009). In this paper, we study the parameterized complexity of these problems. We show that the k - Tuple Domination Problem and the Liar’s Domination Problem are W[2] -hard for general graphs. It can be verified that both the problems have a finite integer index and satisfy certain coverability property. Hence they admit linear kernel as per the meta-theorem in Bodlaender (2009), but the meta-theorem says nothing about the constant. In this paper, we present a direct proof of the existence of linear kernel with small constants for both the problems. [ABSTRACT FROM AUTHOR]

Teramoto et al. [IEICE Trans. Inform. Syst., 89-D (2006), pp. 2348{2356] defined a measure called the gap ratio that measures the uniformity of a finite point set sampled from S, a bounded subset of ℝ². This definition of uniformity measure can be generalized over all metric spaces by appealing to covering and packing radius. We consider discrete spaces like graph and set of points in the Euclidean space and continuous spaces like the unit square and path connected spaces. The definition of the gap ratio needs only a metric unlike discrepancy, a widely used uniformity measure, that depends on the notion of a range space and its volume. We show some interesting connections of the gap ratio to Delaunay triangulation and packing and covering. Asano [Inform. Process. Lett., 109 (2008), pp. 57{60] opined that the discrete version of the uniformity problem makes it amenable to pose combinatorial optimization related questions. The major focus of this work is on finding lower bounds and solving optimization related questions about selecting uniform point samples from metric spaces using the gap ratio. In deducing lower bounds on the gap ratio, we exploit its relation to packing and covering. We have been able to show existence of point configurations with certain cardinality obtained using farthest point insertion and characterized using a recurrence to achieve the lower bounds deduced. Apart from the lower bounds, we prove hardness and approximation hardness results. We show that a general approximation algorithm framework gives different approximation ratios for different metric spaces based on the lower bound we deduce. Apart from the above, we show existence of coresets for sampling uniform points from the Euclidean space—for both the static and the streaming case. This leads to a (1 + ∈)-approximation algorithm for uniform sampling from the Euclidean space. [ABSTRACT FROM AUTHOR]

Primary urinary Bladder Adenocarcinoma (PBA) is an uncommon neoplasm and can cause diagnostic difficulties due to histologic similarities with adenocarcinomas of adjacent structures like Gastrointestinal Tract (GIT) and prostate, since involvement of the bladder by metastasis or direct spread can occur. Seven cases of bladder adenocarcinomas were diagnosed during a period of four years in a tertiary care hospital. Patient's age ranged from 26-78 years with a male predilection. Three cases were signet ring type adenocarcinomas, two cases were subtyped as enteric variant, one as mucinous variant and one as adenocarcinoma Not Otherwise Specified (NOS) variant. One case showed urachal involvement. Common site of involvement was the base and posterior wall of the bladder. Three cases had prior history of GIT malignancy. No morphologic difference was identified to differentiate primary from secondary adenocarcinomas. Bladder adenocarcinoma is rare tumours. Primary and secondary adenocarcinomas cannot be distinguished from each other on morphologic grounds. Ancillary studies may have limited role in distinguishing between the two. Hence, clinical correlation has a major role in their evaluation. [ABSTRACT FROM AUTHOR]

A subset D ⊆ V of a graph G = ( V , E ) is a ( 1 , j ) -set (Chellali et al., 2013) if every vertex v ∈ V ∖ D is adjacent to at least 1 but not more than j vertices in D . The cardinality of a minimum ( 1 , j ) -set of G , denoted as γ ( 1 , j ) ( G ) , is called the ( 1 , j ) -domination number of G . In this paper, using probabilistic methods, we obtain an upper bound on γ ( 1 , j ) ( G ) for j ≥ O ( log Δ ) , where Δ is the maximum degree of the graph. The proof of this upper bound yields a randomized linear time algorithm. We show that the associated decision problem is NP-complete for choral graphs but, answering a question of Chellali et al., provide a linear-time algorithm for trees for a fixed j . Apart from this, we design a polynomial time algorithm for finding γ ( 1 , j ) ( G ) for a fixed j in a split graph, and show that ( 1 , j ) -set problem is fixed parameter tractable in bounded genus graphs and bounded treewidth graphs. [ABSTRACT FROM AUTHOR]

Mucoepidermoid Carcinoma (MEC) is the most common malignant neoplasm of salivary gland origin. However, its morphologic heterogeneity poses difficulty in interpretation. In the present series we discuss the morphologic features of MEC, limitations and pitfalls in its diagnosis on Fine Needle Aspiration Cytology (FNAC). Fourteen cases of suspected MEC were evaluated cytologically followed by histopathological examination for confirmation. A definite cytological diagnosis was rendered in nine cases; three of the remaining five were underdiagnosed as abscess, pleomorphic adenoma and mucus cyst. Of the remaining two cases, one case each of sebaceous carcinoma and sialadenitis was mislabeled as MEC on cytology. A satisfactory aspirate composed of intermediate cells, mucin secreting cells and squamous cells in a mucinous background may not be obtained in all cases of low grade MEC. High grade MEC can be classified as squamous cell carcinoma. Hence, awareness of confounding factors with clinicopathologic correlation and judicious use of frozen section can help in minimizing errors. [ABSTRACT FROM AUTHOR]

The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments with minimum number of sensors. A line segment ℓ is said to be 1-covered if it intersects the sensing region of at least one among the sensors distributed in a bounded rectangular region R. We assume that the sensing radius of each sensor is uniform. The problem of finding the minimum number of sensors needed to 1-cover each member in a given set of line segments in R is NP-hard. We propose two constant factor approximation algorithms and a PTAS (polynomial time approximation scheme) for the problem for 1-covering a set of axis-parallel line segments. We also show that a PTAS exists for 1-covering a set of arbitrarily oriented line segments in R where the lengths of the line segments are bounded within a constant factor of the sensing radius of each sensor. Finally, we propose a constant factor approximation algorithm for k-covering axis-parallel line segments such that sensors maintain a minimum separation among them. [ABSTRACT FROM AUTHOR]

Most of the fingerprint matching techniques require extraction of minutiae that are ridge endings or bifurcations of ridge lines in a fingerprint image. Crucial to this step is either detecting ridges from the gray-level image or binarizing the image and then extracting the minutiae. In this work, we firstly exploit the property of almost equal width of ridges and valleys for binarization. Computing the width of arbitrary shapes is a nontrivial task. So, we estimate the width using Euclidean distance transform (EDT) and provide a near-linear time algorithm for binarization. Secondly, instead of using thinned binary images for minutiae extraction, we detect minutiae straightaway from the binarized fingerprint images using EDT. We also use EDT values to get rid of spurs and bridges in the fingerprint image. Unlike many other previous methods, our work depends minimally on arbitrary selection of parameters. [ABSTRACT FROM AUTHOR]

A new combinatorial feature called Stacked Euler Vector (SERVE) is introduced to characterize a gray-tone image. SERVE comprises a four-tuple, where each element is an integer representing the Euler number of the partial binary image formed by certain pixel overlap relations among the four most significant bit planes of the gray-tone image. Computation of SERVE is simple, fast, and does not involve any floating point operation. SERVE can be used to augment other features to improve the performance of image retrieval significantly. Experimental results on the COIL database are reported to demonstrate its performance. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined -neighborhood region around some point in P. The proposed algorithm for the exact matching needs space and preprocessing time. The existence of a match for a given query set Q can be checked in time in the worst-case, where is the maximum number of equidistant pairs of point in P. For a set of n points, may be in the worst-case. Some applications of the partial point set pattern matching are then illustrated. Experimental results on random point sets and some fingerprint databases show that, in practice, the computation time is much smaller than the worst-case requirement. The algorithm is then extended for checking the exact match of a set of k line segments in the query set with a k-subset of n line segments in the sample set under rigid motion in time. Next, a simple version of the approximate matching problem is studied where one point of Q exactly matches with a point of P, and each of the other points of Q lie in the -neighborhood of some point of P. The worst-case time and space complexities of the proposed algorithm are and , respectively. The proposed algorithms will find many applications to fingerprint matching, image registration, and object recognition. [Copyright &y& Elsevier]

A new combinatorial characterization of a gray-tone image called Euler Vector is proposed. The Euler number of a binary image is a well-known topological feature, which remains invariant under translation, rotation, scaling, and rubber-sheet transformation of the image. The Euler vector comprises a 4-tuple, where each element is an integer representing the Euler number of the partial binary image formed by the gray-code representation of the four most significant bit planes of the gray-tone image. Computation of Euler vector requires only integer and Boolean operations. The Euler vector is experimentally observed to be robust against noise and compression. For efficient image indexing, storage and retrieval from an image database using this vector, a bucket searching technique based on a simple modification of Kd-tree, is employed successfully. The Euler vector can also be used to perform an efficient four-dimensional range query. The set of retrieved images are finally ranked on the basis of Mahalanobis distance measure. Experiments are performed on the COIL database and results are reported. The retrieval success can be improved significantly by augmentiong the Euler vector by a few additional simple shape features. Since Euler vector can be computed very fast, the proposed technique is likely to find many applications to content-based image retrieval. [ABSTRACT FROM AUTHOR]

Abstract: Euler number of a binary image is a fundamental topological feature that remains invariant under translation, rotation, scaling, and rubber-sheet transformation of the image. In this work, a run-based method for computing Euler number is formulated and a new hardware implementation is described. Analysis of time complexity and performance measure is provided to demonstrate the efficiency of the method. The sequential version of the proposed algorithm requires significantly fewer number of pixel accesses compared to the existing methods and tools based on bit-quad counting or quad-tree, both for the worst case and the average case. A pipelined architecture is designed with a single adder tree to implement the algorithm on-chip by exploiting its inherent parallelism. The architecture uses O(N) 2-input gates and requires O(N log N) time to compute the Euler number of an N × N image. The same hardware, with minor modification, can be used to handle arbitrarily large pixel matrices. A standard cell based VLSI implementation of the architecture is also reported. As Euler number is a widely used parameter, the proposed design can be readily used to save computation time in many image processing applications. [Copyright &y& Elsevier]

Many Automatic Fingerprint Identification Systems (AFIS) are based on minutiae matching. Minutiae are the terminations and bifurcations of the ridge lines in a fingerprint image. A gray-scale fingerprint image that has undergone binarization, followed by thinning, in order to extract the minutiae, may contain hundreds of minutiae, all of which are not so vivid and obvious in the original image. Thus, the set of minutiae that are well-defined and more prominent than the rest should be given higher relevance and importance in the process of minutiae matching. In this work, a gray-scale fingerprint image is first preprocessed to produce a thinned binary image. Next, a method to assign a score value to each of the extracted minutiae is proposed, based on certain topographical properties of a minutia. The score associated to a minutia signifies its robustness and prominence. A minutia with a higher score value should be considered with higher priority in the matching scheme to yield better results. Experimental results on several standard databases have been reported. [ABSTRACT FROM AUTHOR]

The database skyline query (or non-domination query) has a spatial form: Given a set P with n point sites, and a point set S of m locations of interest, a site p ∈ P is a skyline point if and only if for each q ∈ P ∖ { p } , there exists at least one location s ∈ S that is closer to p than to q. We reduce the problem of determining skyline points to the problem of finding sites that have non-empty cells in an additively weighted Voronoi diagram under a convex distance function. The weights of said Voronoi diagram are derived from the coordinates of the sites of P , while the convex distance function is derived from the set of locations S. In the two-dimensional plane, this reduction gives an O ((n + m) log ⁡ (n + m)) -time algorithm to find the skyline points. [ABSTRACT FROM AUTHOR]

Neurolymphomatosis is a rare manifestation of non-Hodgkin's lymphoma (NHL) and is characterized by infiltration of the nerves by neoplastic lymphoid cells and is seen in up to 0.2% of all NHL cases. Diagnosing this syndrome is quite a challenge to the hematologists given the vague symptoms and signs and the low incidence. Newer imaging modalities such as positron emission tomography- computed tomography and magnetic resonance imaging have enabled early diagnosis with a sensitivity reaching up to 100%. Despite a variety of therapies reported in the literature for the treatment, the prognosis is very poor. We report a 46-year-old male diagnosed to have NHL-diffuse large B-cell lymphoma and treated with rituximab, cyclophosphamide, vincristine, and prednisolone (R-CHOP) therapy who presented with left brachial plexus neurolymphomatosis as the initial feature of disease relapse. [ABSTRACT FROM AUTHOR]

Abstract: The coverage problem in wireless sensor networks addresses the problem of covering a region with sensors. Many different definitions of coverage are there in the literature depending on the goal of the coverage. In this paper, we address the problem of determining the quality of a sensor deployment against an intruder who can walk along a straight line. A line segment is said to be k-covered if it intersects the sensing regions of at least sensors distributed in . Similarly, it is said to be k-uncovered if it intersects the sensing regions, that is assumed to be circular, of at most sensors. We introduce two new metrics, smallest -covered line segment and longest -uncovered line segment, for measuring the quality of line coverage achieved by a sensor deployment. The intruder can walk a distance less than the smallest -covered line segment without ever being detected by sensors. So, this metric gives an estimate on the distance an intruder can walk in a straight line path before being detected by sensors. On the other side, the defender would want to deploy sensors so that the length of the longest -uncovered line segment is minimized. Given a deployment of sensors, we propose deterministic algorithms to determine the smallest -covered line segment and longest -uncovered line segment where the line segments can be of the following types: (i) axis-parallel (horizontal and vertical) line segments, (ii) line segments whose one endpoint is fixed and is of arbitrary orientation and (iii) arbitrary line segments. The time complexities for the first and second types of line segments are for both smallest -covered line segment and longest -uncovered line segment, where is the number of intersections among circles. For the arbitrary line segment case, the smallest -covered segment can be determined in time, whereas, the longest -uncovered segment can be determined in time, where and is a small value greater than or equal to . All our algorithms take linear space. [Copyright &y& Elsevier]

Quality of Surveillance (QoSv) is a generic measure of the coverage offered by a given network of sensors over the field it monitors. In this work, we consider it to be the length of the longest straight line segment that does not pass through the sensing zone of any sensor. It can be seen as the longest length that an intruder may travel along a straight line, before being detected. An easy to implement algorithm for computing the QoSv in a rectangular field $\mathcal{R}$ containing a set of n identical sensors is proposed. The time and space complexities of our algorithm are O(n2log n) and O(n) respectively. It is also shown that a minor modification of the algorithm runs in O(n2) time and space. [ABSTRACT FROM AUTHOR]

Ensuring different types of coverage is an important problem in many wireless sensor applications. In this paper, we address the problem of maintaining support coverage in the presence of sensor failures. Given a placement of n sensors in an area A, and any two points i and f in A, the support value of any path between i and f is the maximum distance of any point on the path from its closest sensor. The path with the minimum support value is called the maximal support path. The support value of a path may increase if a sensor fails. Given a maximal support path with a support value ψ, we first present two centralized approximation algorithms that, on failure of a single sensor, compute a new path with a support value close to ψ by moving exactly one nearby sensor. The first algorithm assumes that the sensors are allowed to move in any direction, and the second one assumes that the sensors are constrained to move in any of the four directions east, west, north, and south. Both the support value for the new path computed and the movement necessary are shown to be within a constant-factor of the initial support value. We then show that even in case of multiple sensor failures, a new path with a bounded support value can be computed. Detailed simulation results are provided to show that the algorithms result in significant improvement in many cases in practice, and the improvements obtained are significantly better than the worst case bounds given by the analysis. We also discuss distributed implementations of the algorithms. [ABSTRACT FROM AUTHOR]

Abstract: An -dimensional digital binary image () is a function . is connected if and only if its black pixels and white pixels are each ()-connected. is only connected if and only if its black pixels are ()-connected. For a 3-D binary image, the respective connectivity models are and . A pair of ()-neighboring opposite-valued pixels is called interchangeable in a -D binary image , if reversing their values preserves the original connectedness. We call such an interchange to be a -local interchange. Under the above connectivity models, we show that given two binary images of pixels/voxels each, we can transform one to the other using a sequence of -local interchanges. The specific results are as follows. Any two -connected 3-dimensional images and each having black voxels are transformable using a sequence of 26-local interchanges. Here, and are the total number of 8-connected components in all 2-dimensional layers of and respectively. We also show bounds on connectivity under a different interchange model as proposed in [A. Dumitrescu, J. Pach, Pushing squares around, Graphs and Combinatorics 22 (1) (2006) 37–50]. Next, we show that any two simply connected images under the , connectivity model and each having black voxels are transformable using a sequence of 26-local interchanges. We generalize this result to show that any two , -connected -dimensional simply connected images each having black pixels are transformable using a sequence of -local interchanges, where . [Copyright &y& Elsevier]

Recent field-programmable gate array (FPGA) architectures are heterogeneous, owing to the presence of millions of gates in configurable logic blocks (CLBs), block RAMs, and multiplier blocks (MULs) which can host fairly large designs. While their physical design calls for floorplanning, the traditional algorithms for application-specific integrated circuits (ASIC) do not suffice. In this paper, we propose a three-phase algorithm for unified floorplan-topology generation and sizing on heterogeneous FPGAs. The method consists of a recursive balanced bipartitioning followed by the generation of slicing topologies and finally the allocation of CLBs and RAM/MULs to modules by a greedy heuristic and minimum-cost maximum-flow method, respectively. Experimental results on benchmark circuits show that our method HeteroFloorplan produces feasible floorplans within a few seconds with total half-perimeter wirelength (HPWL) improvement of 18%-52% over the very few previous approaches. We also compare our locally greedy CLB allocation with a network-flow formulation to establish its effectiveness. [ABSTRACT FROM AUTHOR]

Presence of kinked transverse colon is not a very common phenomenon. Its presence may not cause physiological disturbance. However, at times when it requires endoscopy, the abrupt looped course of the transverse colon might set a risk of entrapment of the device, which in turn might lead to severe complications and undue discomfort to the patient. An idiopathic kink in the transverse colon of an adult male cadaver was noted and its morphometric and histopathological analysis was performed. The exact location and gross morphometric measurements of the kinks in the transverse colon was recorded. Small pieces of the colon at the regions of kinks were removed, processed, and stained with Haemetoxylin and Eosin, Alcian Blue- Periodic Acid Schiff (PAS) stain and Masson Trichrome stain for histopathological examination. Transverse colon presented with an abrupt loop towards its splenic end by the presence of proximal and distal kinks. Histopathological features of the mucosa at the areas of kink showed foci of surface erosions composed of parallelly placed tubular glands lined by columnar cells, interspersed by goblet cells. Submucosa was oedematous with few congested vessels. Presence of such unusual kink and the loop together may be the cause for forceful forward push of the device introduced into it during colonoscopy and might result in the damage of its mucosa. [ABSTRACT FROM AUTHOR]

Introduction: Osteophytes are bony outgrowth on the vertebral column. Its prevalence in the lumbar region and clinical importance mandates to conduct a detailed study of lumbar osteophytes in the cadaveric vertebral column. Aim: The present study was conducted to study the detailed features of lumbar osteophytes and document its prevalence, morphometric and histological structure. Materials and Methods: This was an observational study in which frequency of occurrence of lumbar osteophytes was studied in 40 cadaveric vertebral columns over a period of four years. The lumbar part of the vertebral columns was dissected and examined meticulously. The occurrence of lumbar osteophytes with their vertebral levels and morphometric measurements were recorded. A small excision of the osteophyte was processed histologically to study its microscopic details using routine Haematoxylin & Eosin stain. Results: Lumbar osteophytes were present in 4 specimens (10%). They were mostly found on the right side of the vertebral bodies. Histopathological examination of the osteophytes revealed degenerative osteophytic cartilage and fibrillation overlying the trabecular bone enclosing fatty marrow spaces containing haematopoietic elements. Conclusion: Lumbar osteophytes were found in 10% of the specimens studied and it is assumed that these cadaveric reports deserve further attention given their potential clinical implications. Knowledge regarding occurrence and incidence of osteophytes is essential for management of common degenerative changes of the vertebral column. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the diffuse reflection diameter and diffuse reflection radius problems for convex-quadrilateralizable polygons. In the usual model of diffuse reflection, a light ray incident at a point on the reflecting surface is reflected from that point in all possible inward directions. A ray reflected from a polygonal edge may graze that reflecting edge but an incident ray cannot graze the reflecting edge. The diffuse reflection diameter of a simple polygon is the minimum number of diffuse reflections that may be needed in the worst case to illuminate any target point from any point light source inside . We show that the diameter is upper bounded by in our usual model of diffuse reflection for convex-quadrilateralizable polygons. To the best of our knowledge, this is the first upper bound on diffuse reflection diameter within a fraction of for such a class of polygons. We also show that the diffuse reflection radius of a convex-quadrilateralizable simple polygon with vertices is at most under the usual model of diffuse reflection. In other words, there exists a point inside such a polygon from which usual diffuse reflections are always sufficient to illuminate the entire polygon. In order to establish these bounds for the usual model, we first show that the diameter and radius are and respectively, for the same class of polygons for a relaxed model of diffuse reflections; in the relaxed model an incident ray is permitted to graze a reflecting edge before turning and reflecting off the same edge at any interior point on that edge. We also show that the worst-case diameter and radius lower bounds of and respectively, are sometimes attained in the usual model, as well as in the relaxed model of diffuse reflection. [Copyright &y& Elsevier]

Euler number is a fundamental topological feature of an image. The efficiency of computation of topological features of an image is critical for many digital imaging applications such as image matching, database retrieval, and computer vision that require real time response. In this paper, a novel algorithm for computing the Euler number of a binary image based on divide-andconquer paradigm, is proposed, which outperforms significantly the conventional techniques used in image processing tools. The algorithm can be easily parallelized for computing the Euler number of an N × N image in O(N) time, with O(N) processors. Using a simple architecture, the proposed method can be implemented as a special purpose VLSI chip to be used as a co-processor. [ABSTRACT FROM AUTHOR]