NDLI: Computing and Verifying Depth Orders

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	de Berg, Mark Schwarzkopf, Otfried Overmars, Mark
Copyright Year	1994
Abstract	A depth order on a set of line segments in 3-space is an order such that line segment a comes before line segment $a'$ in the order when a lies below $a'$ or, in other words, when there is a vertical ray that first intersects $a'$ and then intersects a. Efficient algorithms for the computation and verification of depth orders of sets of n line segments in 3-space are presented. The algorithms run in time $O(n^{{4 / 3} + \varepsilon } )$, for any fixed $\varepsilon > 0$. If all line segments are axis-parallel or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in $O(n\log ^3 n)$, for any fixed $\varepsilon > 0$ time and the verification takes $O(n\log ^2 n)$ time. The algorithms can be generalized to handle triangles and other polygons instead of line segments. They are based on a general framework for computing and verifying linear orders extending implicitly defined binary relations.
Starting Page	437
Ending Page	446
Page Count	10
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539791223747
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	23
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-31
Access Restriction	Subscribed
Subject Keyword	three dimensions depth orders Analysis of algorithms and problem complexity linear extensions of partial orders computational geometry
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

The Union of Convex Polyhedra in Three Dimensions

Low-Dimensional Linear Programming with Violations

Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions

Vertical Ray Shooting and Computing Depth Orders for Fat Objects

Computing Correlation between Piecewise-Linear Functions

Group isomorphism is nearly-linear time for most orders

Functional norms, condition numbers and numerical algorithms in algebraic geometry

Computing Envelopes in Four Dimensions with Applications

Ray Shooting Amidst Spheres in Three Dimensions and Related Problems

Computing and Verifying Depth Orders

Similar Documents

The Union of Convex Polyhedra in Three Dimensions

Low-Dimensional Linear Programming with Violations

Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions

Vertical Ray Shooting and Computing Depth Orders for Fat Objects

Computing Correlation between Piecewise-Linear Functions

Group isomorphism is nearly-linear time for most orders

Functional norms, condition numbers and numerical algorithms in algebraic geometry

Computing Envelopes in Four Dimensions with Applications

Ray Shooting Amidst Spheres in Three Dimensions and Related Problems

Computing and Verifying Depth Orders