A PTAS for Cutting Out Polygons with Lines

We present a simple O(m+n ⁶/ε ¹²) time (1+ε)-approximation algorithm for finding a minimum-cost sequence of lines to cut a convex n-gon out of a convex m-gon.     

New Results on Path Approximation

In this paper we give bounds on the complexity of some algorithms for approximating 2-D and 3-D polygonal paths with the infinite beam measure of error. While the time/space complexities of the algorithms known for other error measures are well understood, path approximation with infinite beam measure seems to be harder due to the complexity of some geometric structures that arise in the known approaches. Our results answer some open problems left in previous work. We also present a more careful analysis of the time complexity of the general iterative algorithm for infinite beam measure and show that it could perform much better in practice than in the worst case. We then propose a new approach for path approximation that consists of a breadth first traversal of the path approximation graph, without constructing the graph. This approach can be applied to any error criterion in any constant dimension. The running time of the new algorithm depends on the size of the output: if the optimal approximating path has m vertices, the algorithm performs F(m) iterations rather than n–1 in the previous approaches, where F(m) \le n–1 is the number of vertices of the path approximation graph that can be reached with at most m–2 edges. This is the first output sensitive path approximation algorithm.     

Flexible Strategies for Disk Scheduling in Multimedia Presentation Servers

Multimedia presentations (e.g., lectures, digital libraries) normally include discrete media objects such as text and images along with continuous media objects such as video and audio. Objects composing a multimedia presentation need to be delivered based on the temporal relationships specified by the author(s). Hence, even discrete media objects (that do not normally have any real-time characteristics) have temporal constraints on their presentations. Composition of multimedia presentations may be light (without any accompanying video or large multimedia data) or heavy (accompanied by video for the entire presentation duration). The varying nature of the composition of multimedia presentations provides some flexibility for scheduling their retrieval. In this paper, we present a min-max skip round disk scheduling strategy that can admit multimedia presentations in a flexible manner depending on their composition. We also outline strategies for storage of multimedia presentations on an array of disks as well as on multi-zone recording disks.Emilda Sindhu received the B.Tech degree in Electrical & Electronics from University of Calicut, India, in 1995 and the M.S. degree in Computer Science in 2003 from National University of Singapore. This paper comprises part of her master thesis work. She is presently employed as Senior Research Officer at the A-star Institute of High Performance Computing (IHPC), Singapore. Her current research interests include distributed computing particulary Grid computing. She is involved in the development of tools and components for distributed computing applications.Lillykutty Jacob obtained her B.Sc (Engg.) degree in electronics and communication from the Kerala University, India, in 1983, M.Tech. degree in electrical engineering (communication) from the Indian Institute of Technology at Madras in 1985, and PhD degree in electrical communication engineering from the Indian Institute of Science, in 1993. She was with the department of computer science, Korea Advanced Institute of Science and Technology, S. Korea, during 1996–97, for post doctoral research, and with the department of Computer Science, National University of Singapore, during 1998–2003, as a visiting faculty. Since 1985 she has been with the National Institute of Technology at Calicut, India, where she is currently a professor. Her research interests include wireless networks, QoS issues, and performance analysis.Ovidiu Daescu received the B.S. in computer science and automation from the Technical Military Academy, Bucharest, Romania, in 1991, and the M.S. and Ph.D. degrees from the University of Notre Dame, in 1997 and 2000. He is currently an Assistant Professor in the Department of Computer Science, University of Texas at Dallas. His research interests are in algorithm design, computational geometry and geometric optimization.B. Prabhakaran is currently with the Department of Computer Science, University of Texas at Dallas. Dr. B. Prabhakaran has been working in the area of multimedia systems: multimedia databases, authoring & presentation, resource management, and scalable web-based multimedia presentation servers. He has published several research papers in prestigious conferences and journals in this area.Dr. Prabhakaran received the NSF CAREER Award FY 2003 for his proposal on Animation Databases. Dr. Prabhakaran has served as an Associate Chair of the ACM Multimedia2003 (November 2003, California), ACM MM 2000 (November 2000, Los Angeles), and ACM Multimedia99 conference (Florida, November 1999). He has served as guest-editor (special issue on Multimedia Authoring and Presentation) for ACM Multimedia Systems journal. He is also serving on the editorial board of Multimedia Tools and Applications journal, Kluwer Academic Publishers. He has also served as program committee member on several multimedia conferences and workshops. Dr. Prabhakaran has presented tutorials in several conferences on topics such as network resource management, adaptive multimedia presentations, and scalable multimedia servers.B. Prabhakaran has served as a visiting research faculty with the Department of Computer Science, University of Maryland, College Park. He also served as a faculty in the Department of Computer Science, National University of Singapore as well as in the Indian Institute of Technology, Madras, India.     

Measurement of the activity of dispersants

A general and quick spectrophotometric method for the determination of activity (and relative activity) of dispersants for disperse and vat dyeing processes is described.     

Efficient Parallel Algorithms for Planar st -Graphs

   Abstract. Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.     

New Results on Path Approximation

In this paper we give bounds on the complexity of some algorithms for approximating 2-D and 3-D polygonal paths with the infinite beam measure of error. While the time/space complexities of the algorithms known for other error measures are well understood, path approximation with infinite beam measure seems to be harder due to the complexity of some geometric structures that arise in the known approaches. Our results answer some open problems left in previous work. We also present a more careful analysis of the time complexity of the general iterative algorithm for infinite beam measure and show that it could perform much better in practice than in the worst case. We then propose a new approach for path approximation that consists of a breadth first traversal of the path approximation graph, without constructing the graph. This approach can be applied to any error criterion in any constant dimension. The running time of the new algorithm depends on the size of the output: if the optimal approximating path has m vertices, the algorithm performs F(m) iterations rather than n–1 in the previous approaches, where F(m) \le n–1 is the number of vertices of the path approximation graph that can be reached with at most m–2 edges. This is the first output sensitive path approximation algorithm.     

The Influence of UV Light on Photodegradation of Acetylsalicylic Acid

Photodegradation of the aqueous solutions of acetylsalicylic acid, in the absence (ASA) and the presence of excipients (ASE), is demonstrated by the photoluminescence (PL). A shift of the PL bands from 342 and 338 nm to 358 and 361–397 nm for ASA and ASE in solid state and as aqueous solutions was reported. By exposure of the solution of ASA 0.3 M to UV light, a decrease in the PL band intensity was highlighted. This behavior was revealed for ASA in the presence of phosphate buffer (PB) having the pH equal to 6.4, 7, and 8 or by the interaction with NaOH 0.3 M. A different behavior was reported in the case of ASE. In the presence of PB, an increase in the intensity of the PL band of ASE simultaneously with a change of the ratio between the intensities of the bands at 361–364 and 394–397 nm was highlighted. The differences between PL spectra of ASA and ASE have their origin in the presence of salicylic acid (SAL). The interaction of ASE with NaOH induces a shift of the PL band at 405–407 nm. Arguments for the reaction of ASA with NaOH are shown by Raman scattering and FTIR spectroscopy.     

Substantivity of anthraquinone vat dyes

The microcrystalline aggregates model of the adsorption of vat dyes on cellulosic materials is substantiated in this study. The relationships between affinities of some anthraquinone vat dye models and van der Waals molecular areas, hydrophobicity and planar-like structures are presented in the form of correlation equations.     

Efficiently Approximating Polygonal Paths in Three and Higher Dimensions

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n -vertex polygonal curve P in \R ^d , d \geq 3 , we approximate P by another poly- gonal curve P' of m ≤ n vertices in \R ^d such that the vertex sequence of P' is an ordered subsequence of the vertices of P . The goal is either to minimize the size m of P' for a given error tolerance \eps (called the min-\# problem), or to minimize the deviation error \eps between P and P' for a given size m of P' (called the min- \eps problem). Our techniques enable us to develop efficient near-quadratic-time algorithms in three dimensions and subcubic-time algorithms in four dimensions for solving the min-\# and min-\eps problems. We discuss extensions of our solutions to d -dimensional space, where d > 4 , and for the L ₁ and L _∈ fty metrics. Received January 10, 1999; revised November 8, 2000.     

Efficient Parallel Algorithms for Planar st-Graphs

Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.