Some Properties of Digital Covering Spaces

In this paper, we study digital versions of some properties of covering spaces from algebraic topology. Among our results are some that correct or improve upon the presentation of assertions in earlier papers (Boxer and Karaca in J. Math. Imaging Vis. 32:23–29, 2008; Han in Inf. Sci. 177:3731–3748, 2007; Han in Inf. Sci. 178:550–561, 2008).     

Connectivity Preserving Multivalued Functions in Digital Topology

We study connectivity preserving multivalued functions (Kovalevsky in A new concept for digital geometry, shape in picture, 1994) between digital images. This notion generalizes that of continuous multivalued functions (Escribano et al. in Discrete geometry for computer imagery, lecture notes in computer science, 2008; Escribano et al. in J Math Imaging Vis 42:76–91, 2012) studied mostly in the setting of the digital plane \({\mathbb {Z}}^2\). We show that connectivity preserving multivalued functions, like continuous multivalued functions, are appropriate models for digital morphological operations. Connectivity preservation, unlike continuity, is preserved by compositions, and generalizes easily to higher dimensions and arbitrary adjacency relations.     

Speed-Up Theorems in Type-2 Computations Using Oracle Turing Machines

A classic result known as the speed-up theorem in machine-independent complexity theory shows that there exist some computable functions that do not have best programs for them (Blum in J. ACM 14(2):322–336, 1967 and J. ACM 18(2):290–305, 1971). In this paper we lift this result into type-2 computations. Although the speed-up phenomenon is essentially inherited from type-1 computations, we observe that a direct application of the original proof to our type-2 speed-up theorem is problematic because the oracle queries can interfere with the speed of the programs and hence the cancellation strategy used in the original proof is no longer correct at type-2. We also argue that a type-2 analog of the operator speed-up theorem (Meyer and Fischer in J. Symb. Log. 37:55–68, 1972) does not hold, which suggests that this curious speed-up phenomenon disappears in higher-typed computations beyond type-2. The result of this paper adds one more piece of evidence to support the general type-2 complexity theory under the framework proposed in Li (Proceedings of the Third International Conference on Theoretical Computer Science, pp. 471–484, 2004 and Proceedings of Computability in Europe: Logical Approach to Computational Barriers, pp. 182–192, 2006) and Li and Royer (On type-2 complexity classes: Preliminary report, pp. 123–138, 2001) as a reasonable setup.     

Superpositions of continuous functions defined on a Baire space

We consider uniformly continuous functions on a Baire space and introduce the notion of a continuity modulus of a function. We formulate a condition on the growth of the continuity modulus φ guaranteeing that superpositions of n-ary functions with continuity modulus φ do not exhaust all (n + 1)-ary functions with continuity modulus φ for any n. Moreover, negating this property leads to the inverse effect.     

The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open

We offer evidence in the disproof of the continuity of the length of minimum inner spanning trees with respect to a parameter vector having a zero component. The continuity property is the key step of the proof of the conjecture in Du and Hwang (Proc. Nat. Acad. Sci. U.S.A. 87:9464–9466, 1990; Algorithmica 7(1):121–135, 1992). Therefore the Steiner ratio conjecture proposed by Gilbert-Pollak (SIAM J. Appl. Math. 16(1):1–29, 1968) has not been proved yet. The Steiner ratio of a round sphere has been discussed in Rubinstein and Weng (J. Comb. Optim. 1:67–78, 1997) by assuming the validity of the conjecture on a Euclidean plane in Du and Hwang (Proc. Nat. Acad. Sci. U.S.A. 87:9464–9466, 1990; Algorithmica 7(1):121–135, 1992). Hence the results in Rubinstein and Weng (J. Comb. Optim. 1:67–78, 1997) have not been proved yet.     

Optimality conditions for multiple objective fractional subset programming with (ρ,σ,θ)-type-I and related non-convex functions

In this paper, we introduce a class of generalized invex n-set functions, called (ρ,σ,θ)-type-I and related non-convex functions, and then establish a number of parametric and semi-parametric sufficient optimality conditions for the primal problem under the aforesaid assumptions. This work partially extends an earlier work of Mishra et al. (Math. Methods Oper. Res. 67, 493–504, 2008) to a wider class of functions.     

An improved data hiding approach for polygon meshes

We present an improved technique for data hiding in polygonal meshes, which is based on the work of Bogomjakov et al. (Comput. Graph. Forum 27(2):637–642, 2008). Like their method, we use an arrangement on primitives relative to a reference ordering to embed a message. But instead of directly interpreting the index of a primitive in the reference ordering as the encoded/decoded bits, our method slightly modifies the mapping so that our modification doubles the chance of encoding an additional bit compared to Bogomjakov et al.’s (Comput. Graph. Forum 27(2):637–642, 2008). We illustrate the inefficiency in the original mapping of Bogomjakov et al. (Comput. Graph. Forum 27(2):637–642, 2008) with an intuitive representation using a binary tree.     

Symbolic Graphs: Linear Solutions to Connectivity Related Problems

The importance of symbolic data structures such as Ordered Binary Decision Diagrams (OBDD) is rapidly growing in many areas of Computer Science where the large dimensions of the input models is a challenging feature: OBDD based graph representations allowed to define truly new standards in the achievable dimensions for the Model Checking verification technique. However, OBDD representations pose strict constraints in the algorithm design issue. For example, Depth-First Search (DFS) is not feasible in a symbolic framework and, consequently, many state-of-the-art DFS based algorithms (e.g., connectivity procedures) cannot be easily rearranged to work on symbolically represented graphs. We devise here a symbolic algorithmic strategy, based on the new notion of spine-set, that is general enough to be the engine of linear symbolic step algorithms for both strongly connected components and biconnected components. Our procedures improve on previously designed connectivity symbolic algorithms. Moreover, by an application to the so-called “bad cycle detection problem”, our technique can be used to efficiently solve the emptiness problem for various kinds of ω-automata. This work is a revised and extended version of [22,23]. It is partially supported by the projects PRIN 2005015491 and BIOCHECK.     

Edge Pricing of Multicommodity Networks for Selfish Users with Elastic Demands

We examine how to induce selfish heterogeneous users in a multicommodity network to reach an equilibrium that minimizes the social cost. In the absence of centralized coordination, we use the classical method of imposing appropriate taxes (tolls) on the edges of the network. We significantly generalize previous work (Yang and Huang in Transp. Res. Part B 38:1–15, [2004]; Karakostas and Kolliopoulos in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 268–276, [2004]; Fleischer et al. in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 277–285, [2004]) by allowing user demands to be elastic. In this setting the demand of a user is not fixed a priori but it is a function of the routing cost experienced, a most natural assumption in traffic and data networks. Research supported by MITACS and a NSERC Discovery grant.     

Investigating the usability of real-time scheduling theory with the Cheddar project

This article deals with real-time critical systems modelling and verification. Real-time scheduling theory provides algebraic methods and algorithms in order to make timing constraints verifications of these systems. Nevertheless, many industrial projects do not perform analysis with real-time scheduling theory even if demand for use of this theory is large and the industrial application field is wide (avionics, aerospace, automotive, autonomous systems, …). The Cheddar project investigates why real-time scheduling theory is not used and how its usability can be increased. The project was launched at the University of Brest in 2002. In Lecture Notes on Computer Sciences, vol. 5026, pp. 240–253, 2008, we have presented a short overview of this project. This article is an extended presentation of the Cheddar project, its contributions and also its ongoing works.     

Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

A survey of recursive analysis and Moore’s notion of real computation

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore’s class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230–265, 1936), Grzegorczyk (Fundam Math 42:168–202, 1955), and Lacombe (Compt Rend l’Acad Sci Paris 241:151–153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore’s class and the relationships between them.     

Accurate Camera Calibration from Multi-View Stereo and Bundle Adjustment

The advent of high-resolution digital cameras and sophisticated multi-view stereo algorithms offers the promise of unprecedented geometric fidelity in image-based modeling tasks, but it also puts unprecedented demands on camera calibration to fulfill these promises. This paper presents a novel approach to camera calibration where top-down information from rough camera parameter estimates and the output of a multi-view-stereo system on scaled-down input images is used to effectively guide the search for additional image correspondences and significantly improve camera calibration parameters using a standard bundle adjustment algorithm (Lourakis and Argyros 2008). The proposed method has been tested on six real datasets including objects without salient features for which image correspondences cannot be found in a purely bottom-up fashion, and objects with high curvature and thin structures that are lost in visual hull construction even with small errors in camera parameters. Three different methods have been used to qualitatively assess the improvements of the camera parameters. The implementation of the proposed algorithm is publicly available at Furukawa and Ponce (2008b).     

Using Biologically Inspired Features for Face Processing

In this paper, we show that a new set of visual features, derived from a feed-forward model of the primate visual object recognition pathway proposed by Riesenhuber and Poggio (R&P Model) (Nature Neurosci. 2(11):1019–1025, 1999) is capable of matching the performance of some of the best current representations for face identification and facial expression recognition. Previous work has shown that the Riesenhuber and Poggio Model features can achieve a high level of performance on object recognition tasks (Serre, T., et al. in IEEE Comput. Vis. Pattern Recognit. 2:994–1000, 2005). Here we modify the R&P model in order to create a new set of features useful for face identification and expression recognition. Results from tests on the FERET, ORL and AR datasets show that these features are capable of matching and sometimes outperforming other top visual features such as local binary patterns (Ahonen, T., et al. in 8th European Conference on Computer Vision, pp. 469–481, 2004) and histogram of gradient features (Dalal, N., Triggs, B. in International Conference on Computer Vision & Pattern Recognition, pp. 886–893, 2005). Having a model based on shared lower level features, and face and object recognition specific higher level features, is consistent with findings from electrophysiology and functional magnetic resonance imaging experiments. Thus, our model begins to address the complete recognition problem in a biologically plausible way.     

Non-Uniform Reductions

We study properties of non-uniform reductions and related completeness notions. We strengthen several results of Hitchcock and Pavan (ICALP (1), Lecture Notes in Computer Science, vol. 4051, pp. 465–476, Springer, 2006) and give a trade-off between the amount of advice needed for a reduction and its honesty on NEXP. We construct an oracle relative to which this trade-off is optimal. We show, in a more systematic study of non-uniform reductions, among other things that non-uniformity can be removed at the cost of more queries. In line with Post’s program for complexity theory (Buhrman and Torenvliet in Bulletin of the EATCS 85, pp. 41–51, 2005) we connect such ‘uniformization’ properties to the separation of complexity classes.     

Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems

We give the first algorithm for testing the feasibility of a system of sporadic real-time tasks on a set of identical processors, solving an open problem in the area of multiprocessor real-time scheduling (Baruah and Pruhs in Journal of Scheduling 13(6):577–582, 2009). We also investigate the related notion of schedulability and a notion that we call online feasibility. Finally, we show that discrete-time schedules are as powerful as continuous-time schedules, which answers another open question in the above mentioned survey.     

U-multimedia framework: a secure and intelligent multimedia service framework based on context information in U-home

In the last few years, intelligent secured multimedia services play a vital role along with ubiquitous home environment (Park et al. in Lecture Notes in Computer Science, vol. 4097, pp. 660–670, [2006]; Lecture Notes in Computer Science, vol. 4159, pp. 893–901, [2006]; IEICE Trans. Inf. Syst. E89-D(12):2831–2837, [2006]; Lecture Notes in Artificial Intelligence, vol. 4252, pp. 777–784, [2006]; Lecture Notes in Artificial Intelligence, vol. 3801, pp. 313–320, [2005]). There are certain constrains and limitations in providing effective and efficient services in U-home. The mechanism and applications are integrated to realize such services. Three different kinds of ubiquitous multimedia services are proposed in the framework. Based on the temporal and spatial context information, the surrounding situations are recognized. The contexts are collected and well analyzed with the preconditions to provide the final services. The proposed framework provides efficient services in the multimedia based deices based on the current context information.

Planar Polyline Drawings via Graph Transformations

We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where W ￡ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor , and W+H ￡ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor . It uses at most ?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2).     

An improved adaptive sampling scheme for the construction of explicit boundaries

This article presents an improved adaptive sampling scheme for the construction of explicit decision functions (constraints or limit state functions) using Support Vector Machines (SVMs). The proposed work presents substantial modifications to an earlier version of the scheme (Basudhar and Missoum, Comput Struct 86(19–20):1904–1917, 2008). The improvements consist of a different choice of samples, a more rigorous convergence criterion, and a new technique to select the SVM kernel parameters. Of particular interest is the choice of a new sample chosen to remove the “locking” of the SVM, a phenomenon that was not understood in the previous version of the algorithm. The new scheme is demonstrated on analytical problems of up to seven dimensions.     

Properties of Digital Homotopy

Several recent papers have adapted notions of geometric topology to the emerging field of digital topology. An important notion is that of digital homotopy. In this paper, we study a variety of digitally-continuous functions that preserve homotopy types or homotopy-related properties such as the digital fundamental group.Laurence Boxer is Professor of Computer and Information Sciences at Niagara University, and Research Professor of Computer Science and Engineering at the State University of New York at Buffalo. He received his Ph.D. in Mathematics from the University of Illinois at Urbana-Champaign. His research interests are computational geometry, parallel algorithms, and digital topology. Dr. Boxer is co-author, with Russ Miller, of Algorithms Sequential and Parallel, A Unified Approach, a recent textbook published by Prentice Hall.