NDLI: The partition technique for overlays of envelopes

Content Provider	IEEE Xplore Digital Library
Author	Koltun, V. Sharir, M.
Copyright Year	2002
Description	Author affiliation: Sch. of Comput. Sci., Tel Aviv Univ., Israel (Koltun, V.; Sharir, M.)
Abstract	We obtain a near-tight bound of O(n/sup 3+/spl epsiv//), for any /spl epsiv/ > 0, on the complexity of the overlay of the minimization diagrams of two collections of surfaces in four dimensions. This settles a long-standing problem in the theory of arrangements, most recently cited by Agarwal and Sharir (2000), and substantially improves and simplifies a result previously published by the authors (2002). Our bound has numerous algorithmic and combinatorial applications, some of which are presented in this paper. Our result is obtained by introducing a new approach to the analysis of combinatorial structures arising in geometric arrangements of surfaces. This approach, which we call the 'partition technique', is based on k-fold divide and conquer, in which a given collection /spl Fscr/ of n surfaces is partitioned into k subcollections /spl Fscr//sub i/ of n/k surfaces each, and the complexity of the relevant combinatorial structure in /spl Fscr/ is recursively related to the complexities of the corresponding structures in each of the /spl Fscr//sub i/'s. We introduce this approach by applying it first to obtain a new simple proof for the known near-quadratic bound on the complexity of an overlay of two minimization diagrams of collections of surfaces in /spl Ropf//sup 3/, thereby simplifying the previously available proof (1996).
Sponsorship	IEEE Comput. Soc. Tech. Committee on Maht. Found. Comput. (TCMF) ACM/SIGACT
Starting Page	637
Ending Page	646
File Size	399291
Page Count	10
File Format	PDF
ISBN	0769518222
ISSN	02725428
DOI	10.1109/SFCS.2002.1181989
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-11-19
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer science Polynomials Geometry
Content Type	Text
Resource Type	Article

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 Partition Technique for Overlays of Envelopes

The partition technique for overlays of envelopes

The partition technique for overlays of envelopes

A Computational Framework for the Study of Partition Functions and Graph Polynomials

On Overlays and Minimization Diagrams

On overlays and minimization diagrams

Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials

An Optimal Algorithm for Computing Visibility in the Plane

Factoring Rational Polynomials over the Complex Numbers

The partition technique for overlays of envelopes

Similar Documents

The Partition Technique for Overlays of Envelopes

The partition technique for overlays of envelopes

The partition technique for overlays of envelopes

A Computational Framework for the Study of Partition Functions and Graph Polynomials

On Overlays and Minimization Diagrams

On overlays and minimization diagrams

Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials

An Optimal Algorithm for Computing Visibility in the Plane

Factoring Rational Polynomials over the Complex Numbers

The partition technique for overlays of envelopes