Capturing crossings: Convex hulls of segment and plane intersections

We give a simple O(nlogn) algorithm to compute the convex hull of the (possibly Θ(n²)) intersection points in an arrangement of n line segments in the plane. We also show an arrangement of dn hyperplanes in d-dimensions whose arrangement has Θ(nd−1) intersection points on the convex hull.     

Static virtualization of C source code

Many existing systems are written in C and are not re‐entrant or thread safe. Sometimes these systems are required in a context for which they were not first designed, possibly meaning they now need to be re‐entrant. This article introduces a program that filters C source code, modifying shared resources (the global variables) to make the code re‐entrant: ‘virtualizing’ the code. The code is then compiled as normal. This approach allows programmatic virtualization with little cost at runtime. Copyright © 2007 John Wiley & Sons, Ltd.     

Agile Spectrum Imaging: Programmable Wavelength Modulation for Cameras and Projectors

We advocate the use of quickly‐adjustable, computer‐controlled color spectra in photography, lighting and displays. We present an optical relay system that allows mechanical or electronic color spectrum control and use it to modify a conventional camera and projector. We use a diffraction grating to disperse the rays into different colors, and introduce a mask (or LCD/DMD) in the optical path to modulate the spectrum. We analyze the trade‐offs and limitations of this design, and demonstrate its use in a camera, projector and light source. We propose applications such as adaptive color primaries, metamer detection, scene contrast enhancement, photographing fluorescent objects, and high dynamic range photography using spectrum modulation.     

Grouping Techniques for Scheduling Problems: Simpler and Faster

In this paper we describe a general grouping technique to devise faster and simpler approximation schemes for several scheduling problems. We illustrate the technique on two different scheduling problems: scheduling on unrelated parallel machines with costs and the job shop scheduling problem. The time complexity of the resulting approximation schemes is always linear in the number n of jobs, and the multiplicative constant hidden in the O(n) running time is reasonably small and independent of the error ε. Supported by Swiss National Science Foundation project 200020-109854, “Approximation Algorithms for Machine scheduling Through Theory and Experiments II”. A preliminary version of this paper appeared in the Proceedings of ESA’01.     

Delineating Boundaries for Imprecise Regions

In geographic information retrieval, queries often name geographic regions that do not have a well-defined boundary, such as “Southern France.” We provide two algorithmic approaches to the problem of computing reasonable boundaries of such regions based on data points that have evidence indicating that they lie either inside or outside the region. Our problem formulation leads to a number of subproblems related to red-blue point separation and minimum-perimeter polygons, many of which we solve algorithmically. We give experimental results from our implementation and a comparison of the two approaches. This research is supported by the EU-IST Project No. IST-2001-35047 (SPIRIT) and by grant WO 758/4-2 of the German Research Foundation (DFG).     

Observed finger behaviour during computer mouse use

Two-button computer mouse users may exhibit sustained, static finger lifting behaviours to prevent inadvertent activations by avoiding finger pressure on the buttons, which leads to prolonged, static finger extensor muscle loading. One hundred graduate students were observed during normal computer work in a university computer facility to qualify and quantify the prevalence of lifted finger behaviours and extended finger postures, as well as wrist/forearm and grip behaviour, during specific mouse activities. The highest prevalences observed were 48% of the students lifted their middle finger during mouse drag activities, and 23% extended their middle finger while moving the mouse. In addition, 98% of the students rested their wrist and forearm (77%) or wrist only (21%) on the workstation surface, and 97% had an extended wrist posture (15 degrees -30 degrees ) when using the mouse. Potential applications of these findings include future computer input device designs to reduce finger lifting behaviour and exposures to risk factors of hand/forearm musculoskeletal pain.     

远大前程——阿尔派“水”与争锋

每年1月,汽车音响行业都会翘首以盼阿尔派音响改装样板车问世。一般,在拉斯维加斯的国际消费类电子产品展览会(CES)上,阿尔派设计人员都会向人们展示其样板车。在过     

碳纤维低音箱制作

时下,石油的价格飚升,经济持续低迷。也许,我们(包括汽车音响发烧友)都需要采取一些砍掉成本的措施。多年来,我决定采取升级改装的汽车。汽车的其余部位拥有大量的碳纤维,我打算使用碳纤维制作低音箱,使之符合配合主题元素。同时,箱体的重量越轻越好。我拿来另一改装车用剩下来的一块12英寸的聚氯乙烯(PVC),用它来包裹箱体。箱体是由6061铝、碳纤维及少许环氧混合制作而成。