On the intrinsic complexity of point finding in real singular hypersurfaces
In previous work we designed an efficient procedure that finds an algebraic sample point for each connected component of a smooth real complete intersection variety. This procedure exploits geometric properties of generic polar varieties and its complexity is intrinsic with respect to the problem. I...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier
2009
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 07227caa a22007937a 4500 | ||
|---|---|---|---|
| 001 | PAPER-23085 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518205443.0 | ||
| 008 | 190411s2009 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-69249212180 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a IFPLA | ||
| 100 | 1 | |a Bank, B. | |
| 245 | 1 | 3 | |a On the intrinsic complexity of point finding in real singular hypersurfaces |
| 260 | |b Elsevier |c 2009 | ||
| 270 | 1 | 0 | |m Heintz, J.; Departamento de Computación, Universidad de Buenos Aires, CONICET, Pab. I, 1428 Ciudad Autonoma de Buenos Aires, Argentina; email: joos@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties, real equation solving and data structures: The hypersurface case (1997) J. Complexity, 13, pp. 5-27. , (Best Paper Award J. Complexity 1997) | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Z., 238, pp. 115-144 | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties and an efficient real elimination procedure (2004) Kybernetika (Prague), 40, pp. 519-550 | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties: Geometry and algorithms (2005) J. Complexity, 21, pp. 377-412 | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Safey El Din, M., Schost, E., On the geometry of polar varieties, AAECC (2009), , http://www.mathematik.hu-berlin.de/publ/pre/2009/P-09-10.pdf, submitted for publication | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Variétés bipolaires et résolution d'une équation polynomiale réelle, , http://www.mathematik.hu-berlin.de/publ/pre/2009/P-09-06.pdf, Preprint 09-06, Mathematisches Institut, Humboldt-Universität zu Berlin, 2009 | ||
| 504 | |a Basu, S., Pollack, R., Roy, M.-F., (2006) Algorithms in Real Algebraic Geometry. 2nd ed., , Springer-Verlag, Berlin | ||
| 504 | |a Brasselet, J.P., Milnor Classes via Polar Varieties (2000) Contemp. Math., 266. , AMS pp. 181-187 | ||
| 504 | |a Canny, J.F., Some algebraic and geometric computations (1988) PSPACE, Proc. 20th ACM Symp. on Theory of Computing, pp. 460-467 | ||
| 504 | |a Canny, J.F., The Complexity of Robot Motion Planning (1988) ACM Doctoral Dissertation Awards, 19. , MIT Press, Cambridge, MA | ||
| 504 | |a Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3, pp. 347-420 | ||
| 504 | |a Grigor'ev, D., Vorobjov, N., Solving systems of polynomial inequalities in subexponential time (1988) J. Symbolic Comput., 5, pp. 37-64 | ||
| 504 | |a Heintz, J., Kuijpers, B., Constraint databases, data structures and efficient query evaluation (2004) Lecture Notes in Computer Science, 3074, pp. 1-24. , Constraint Databases. First International Symposium, Proceedings. Bart K., et al. (Ed). CDB 2004, Paris, France, June 12-13, 2004, Springer, Berlin | ||
| 504 | |a Heintz, J., Roy, M.F., Solernó, P., On the complexity of semialgebraic sets (1989) IFIP Information Processing, 89, pp. 293-298. , Ritter G.X. (Ed), Elsevier | ||
| 504 | |a Heintz, J., Roy, M.-F., Solernó, P., Single exponential path finding in semialgebraic sets. Part I: The case of a regular bounded hypersurface (1991) Lecture Notes in Comput. Sci., 508, pp. 180-196. , Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proc. of the 8th Intern. Conf. AAECC. Tokyo, 1990. Sakata S. (Ed), Springer | ||
| 504 | |a Piene, R., Polar classes of singular varieties (1978) Ann. Sci. École Norm. Sup. 4. Sér., 11, pp. 247-276 | ||
| 504 | |a Renegar, J., A faster PSPACE algorithm for deciding the existential theory of the reals (1988) 29th Ann. Symposium on Foundations of Computer Science, pp. 291-295 | ||
| 504 | |a Safey El Din, M., (2005) Finding sampling points on real hypersurfaces is easier in singular situations, , http://www-spiral.lip6.fr/~safey/publi.html, prepublication | ||
| 504 | |a Safey El Din, M., Schost, E., Properness defects of projections and computation of at least one point in each connected component of a real algebraic set (2004) J. Discrete Comput. Geom., 32, pp. 417-430 | ||
| 504 | |a Safey El Din, M., Trebuchet, P., Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry, , http://arxiv.org/abs/cs/0610051 | ||
| 504 | |a Safey El Din, M., Schost, E., (2009) A baby steps/giant steps Monte Carlo algorithm for computing roadmaps in smooth compact real hypersurfaces, , arXiv:0902.1612v1 | ||
| 504 | |a Teissier, B., Quelques points de l'histoire des variétés polaires, de Poncelet à nos jours (1988) Sémin. Anal. 1987-1988, 4. , Univ. Blaise Pascal | ||
| 520 | 3 | |a In previous work we designed an efficient procedure that finds an algebraic sample point for each connected component of a smooth real complete intersection variety. This procedure exploits geometric properties of generic polar varieties and its complexity is intrinsic with respect to the problem. In the present paper we introduce a natural construction that allows to tackle the case of a non-smooth real hypersurface by means of a reduction to a smooth complete intersection. © 2009 Elsevier B.V. All rights reserved. |l eng | |
| 593 | |a Humboldt-Universität zu Berlin, Institut für Mathematik, D-10099 Berlin, Germany | ||
| 593 | |a CNRS, École Polytechnique, Laboratoire LIX, F-91228 Palaiseau Cedex, France | ||
| 593 | |a Departamento de Computación, Universidad de Buenos Aires, CONICET, Pab. I, 1428 Ciudad Autonoma de Buenos Aires, Argentina | ||
| 593 | |a Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, 39071 Santander, Spain | ||
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a REAL POLYNOMIAL EQUATION SOLVING |
| 690 | 1 | 0 | |a SINGULAR HYPERSURFACE |
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a COMPUTER APPLICATIONS |
| 690 | 1 | 0 | |a DATA PROCESSING |
| 690 | 1 | 0 | |a COMPLETE INTERSECTION |
| 690 | 1 | 0 | |a CONNECTED COMPONENT |
| 690 | 1 | 0 | |a GEOMETRIC PROPERTIES |
| 690 | 1 | 0 | |a HYPER-SURFACES |
| 690 | 1 | 0 | |a HYPERSURFACE |
| 690 | 1 | 0 | |a REAL POLYNOMIAL EQUATION SOLVING |
| 690 | 1 | 0 | |a SAMPLE POINT |
| 690 | 1 | 0 | |a POLYNOMIALS |
| 700 | 1 | |a Giusti, M. | |
| 700 | 1 | |a Heintz, J. | |
| 700 | 1 | |a Pardo, L.M. | |
| 773 | 0 | |d Elsevier, 2009 |g v. 109 |h pp. 1141-1144 |k n. 19 |p Inf. Process. Lett. |x 00200190 |w (AR-BaUEN)CENRE-1599 |t Information Processing Letters | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-69249212180&doi=10.1016%2fj.ipl.2009.07.014&partnerID=40&md5=0a733cd592df6a24912cc2f757ac4fd1 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.ipl.2009.07.014 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_00200190_v109_n19_p1141_Bank |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v109_n19_p1141_Bank |y Registro en la Biblioteca Digital |
| 961 | |a paper_00200190_v109_n19_p1141_Bank |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 84038 | ||