NDLI: Predicates for line transversals to lines and line segments in three-dimensional space

Please wait, while we are loading the content...

Dynamic coresets

Tighter bounds for random projections of manifolds

The complexity of the outer face in arrangements of random segments

A (slightly) faster algorithm for klee's measure problem

I/o-efficient efficient algorithms for computing contours on a terrain

Exact geometric-topological analysis of algebraic surfaces

On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphism

Arrangements of geodesic arcs on the sphere

Towards persistence-based reconstruction in euclidean spaces

Locally uniform anisotropic meshing

A simple and efficient kinetic spanner

Fast enumeration algorithms for non-crossing geometric graphs

Consistent digital rays

Delaunay triangulations of polyhedral surfaces, a discrete Laplace-Beltrami operator and applications

Optimizing active ranges for consistent dynamic map labeling

Markov convexity and local rigidity of distorted metrics

On s-intersecting curves and related problems

Walking your dog in the woods in polynomial time

External memory planar point location with logarithmic updates

Predicates for line transversals to lines and line segments in three-dimensional space

New existence proofs ε-nets

Delpsc: a delaunay mesher for piecewise smooth complexes

Reeb spaces of piecewise linear mappings

Discrete laplace operator on meshed surfaces

Schnyder woods for higher genus triangulated surfaces

Polychromatic colorings of plane graphs

Combinatorial genericity and minimal rigidity

Geometry is everywhere, part XLVII: metrics, nets, dimensions, and measures

Maximum thick paths in static and dynamic environments

Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs

On levels in arrangements of curves, iii: further improvements

Hinged dissections exist

Self-improving algorithms for delaunay triangulations

Robust construction of the three-dimensional flow complex

Extremal problems on triangle areas in two and three dimensions

On the computation of 3d periodic triangulations

Testing contractibility in planar rips complexes

Untangling triangulations through local explorations

Embedding and similarity search for point sets under translation

Coloring $k_{k}-free$ intersection graphs of geometric objects in the plane

Improved upper bounds on the crossing number

Circular partitions with applications to visualization and embeddings

Helly-type theorems for approximate covering

Markov incremental constructions

Visualizing and exploring planar algebraic arrangements: a web application

Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space

Delaunay triangulations of imprecise pointsin linear time after preprocessing

Intersecting convex sets by rays

Analyzing rigidity with pebble games

Minkowski sums of rotating convex polyhedra

Routing a maximum number of disks through a scene of moving obstacles

Predicates for line transversals to lines and line segments in three-dimensional space

Content Provider	ACM Digital Library
Author	Glisse, Marc Lazard, Sylvain Devillers, Olivier
Abstract	When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are transversals to some edges of the polyhedra. In this paper we investigate predicates about visibility events arising in this context. Namely, we consider the predicates for counting the number of line transversals to lines and segments in 3D and the predicate for determining whether a line of sight is intersected by a triangle. We also consider a predicate that order these visibility events in the rotating plane-sweep algorithm of Brönnimann et al. (2007) We present a new approach for solving these predicates and show that the degree of the resulting procedures are significantly smaller than the naive approach based on Plücker coordinates. All the degrees are considered here in the Cartesian coordinates of the points defining the lines and segments. In particular, we present a procedure of degree 12 (resp. 15) for determining the number of transversals to four (resp. five or more) segments. We present procedures of degree 15 for the occlusion predicate and of degree 36 for the ordering predicate. In comparison, the degree of the standard procedure based on the Plücker coordinates for solving these predicates range from 36 to 168 [Everett et al. 2006].
Starting Page	174
Ending Page	181
Page Count	8
File Format	PDF
ISBN	9781605580715
DOI	10.1145/1377676.1377704
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Polynomial Line transversal Optimality Predicate
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in